trees, LL, Flashcards
iterative in order traversal
–
binary tree in order traversal
don’t code
review
https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
don’t code
review
https://leetcode.com/problems/diameter-of-binary-tree/description/
code!!
helper func returns [height, diam].
height = 1 + max(left height, right height)
diam = max ( max(left diam, right diam), left height + right height )
https://leetcode.com/problems/balanced-binary-tree/description/
don’t code
review
https://leetcode.com/problems/subtree-of-another-tree/description/
given root and subroot, det whether the tree w/ head subroot is contained within the tree w/ head root
don’t code but must review logic
use isSameTree() helper func. call it whenever root.val == subRoot.val. if !isSameTree, DON’T return false immediately; keep going down the tree
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/
don’t code but must review logic
head of the tree is the middle element in the array. head.left = middle element of left half. head.left = middle element of right half.
https://leetcode.com/problems/path-sum/description/
code
must do the node.left == null && node.right == null check; if the only check is done for node == null, cases will be missed
https://leetcode.com/problems/construct-string-from-binary-tree/
code
use string.join(“”, list.subList()) to get rid of outer ( ).
only add ( ) for a null child in the case of a null left child and non-null right child
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
of binary SEARCH tree, not binary tree
don’t code but must review logic
if we encounter a node whose val is == to the vals of either of the input nodes, immediately return.
lca can also be a node whose value is btwn the two nodes. traverse bst by comparing the node’s val to greater and lesser
https://leetcode.com/problems/insert-into-a-binary-search-tree/description/
don’t code but must review logic
no need for fancy insertions; just insert where there is a null node.
if (val < node.val and node.left == null), insert node there and break.
traverse bst based on property.
https://leetcode.com/problems/delete-node-in-a-bst/description/
code and review logic!!
if (val > curr.val), curr.right = recurse(curr.right, val).
same for <.
if ==, first handle cases where curr has a null child.
if it doesn’t, we replace curr.val with the val of the rightmost node in curr’s left subtree (or the leftmost node in the right subtree - either works).
then, make a recursive call on whichever subtree you took the value from
https://leetcode.com/problems/count-good-nodes-in-binary-tree/
don’t code but must review logic
helper function takes in node, info, and greatestVal.
if node.val >= greatestVal, update info.
update greatestVal accordingly.
https://leetcode.com/problems/validate-binary-search-tree/description/
don’t code but must review logic
create a helper function. must pass in min valid value and max valid value into it
https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/
code!!
.
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
code and review logic
remember these two key observations:
- the first element in the preorder array is always the root
- find the value of the root in the inorder array. everything to the left of that value is in the root’s left subtree; everything to the right is in the root’s right subtree.
splitIdx also reveals where the split occurs in the preorder array - [1, mid] in preorder is left subtree
use Arrays.copyOfRange to get subarrays
https://leetcode.com/problems/unique-binary-search-trees/
code helper func only, and review logic
use caching.
num trees i can make w/ 3 nodes =
(remember 1 root node!)
(num trees with 0 nodes in left subtree * num trees with 2 in right)
+
(1 node in left * 1 node in right)
+ …
2 base cases: (0, 1) and (1, 1)
https://leetcode.com/problems/sum-root-to-leaf-numbers/description/
don’t code but must review logic
use global var sum.
pass an int ‘path’ into the helper function. path = 10 * path + node.val.
https://leetcode.com/problems/house-robber-iii/description/
code and review logic
instead of tracking the sum from top to bottom, consider it from bottom to top
helper function returns [nodeInc, nodeExc].
no need to keep track of sum variable; just return max of the result [ ] in the main function
nodeExc = max(both left) + max(both right)
nodeIncluded = node.val + left[1] + right[1];
https://leetcode.com/problems/flip-equivalent-binary-trees/description/
don’t code; review logic of return stmt only
.
https://leetcode.com/problems/all-possible-full-binary-trees/description/
code and review logic
- full binary trees can’t have even num of nodes.
- BC n = 1. the tree just has 1 node.
- num nodes in left subtree is in the range [1, n - 2]
https://leetcode.com/problems/trim-a-binary-search-tree/description/
code and review logic
it’s a BST so if a node has a value too large, all of its right subtree must be cut, and if a node has a value too small, all of its left subtree must be cut.
when you encounter a node that must be cut, you must traverse the tree until you reach a valid node
https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/description/
don’t code but must review logic
must use gloval var for sum
review code
https://leetcode.com/problems/binary-search-tree-iterator/description/
code and review logic
when adding to stack in the constructor, always go left, starting from root. we never add all of the nodes to the stack; only O(h) space
in the next() func, pop a node off the stack, get its right child, and then go left adding to stack
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/
code and review logic
PRE order traversal
use global var for index.
split serialized string at commas.
https://leetcode.com/problems/binary-tree-maximum-path-sum/
code and review logic
get L and R from recursive calls.
maxBranch = max ( max(L, R) + node.val , node.val). this is also the return value
maxOverall = (L + R + node.val, maxBranch)
update global var sum as needed.
reverse LL iterative and recursive
code
.
https://leetcode.com/problems/palindrome-linked-list/description/
don’t code; review logic
at the beginning, must include
if (head == null || head.next == null) return true;
https://leetcode.com/problems/remove-linked-list-elements/description/
don’t code; review logic
use dummy head. if node.val != val, curr.next = node and move both ptrs forward.
MUST REMEMBER curr.next = null after while loop exits. otherwise, elements at the end won’t be removed
https://leetcode.com/problems/intersection-of-two-linked-lists/description/
code again
.
https://leetcode.com/problems/reorder-list/description/
don’t code; review logic
- reverse list starting from mid. then it becomes clear how to merge
- review order of reassigning and advancing pointers
- handle case of odd length list
https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
don’t code; review logic
advance fast ptr n times (while fast is not null and n– > 0). use dummy head to avoid handling edge cases.
https://leetcode.com/problems/check-completeness-of-a-binary-tree/description/
the idea is that once you encounter a null node, all nodes after it in the queue must also be null
have a boolean nullEncountered outside the main loop
https://leetcode.com/problems/maximum-width-of-binary-tree/
bfs. add to queue(Item(node, idx))
idx of a node’s left child = idx * 2
idx of a node’s right child = idx * 2 + 1
https://leetcode.com/problems/convert-bst-to-greater-tree/description/
sum must be in Info class
https://leetcode.com/problems/find-duplicate-subtrees/description/
serialization = cur.val + “,” + postorder(cur.left, map, res) + “,” + postorder(cur.right, map, res);
return this serialization in the helper function
https://leetcode.com/problems/minimum-distance-between-bst-nodes/description/
review logic
traverse the tree in this way:
left
add to list
right
now you have a list of all tree values in sorted order. get min difference
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
bfs. to insert right to left:
level.add(0, node.val);
