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!!
.