trees, LL, Flashcards

1
Q

iterative in order traversal

A

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

binary tree in order traversal

don’t code

A

review

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

review

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

https://leetcode.com/problems/diameter-of-binary-tree/description/

code!!

A

helper func returns [height, diam].

height = 1 + max(left height, right height)

diam = max ( max(left diam, right diam), left height + right height )

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

https://leetcode.com/problems/balanced-binary-tree/description/

don’t code

A

review

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

use isSameTree() helper func. call it whenever root.val == subRoot.val. if !isSameTree, DON’T return false immediately; keep going down the tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/

don’t code but must review logic

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

https://leetcode.com/problems/path-sum/description/

code

A

must do the node.left == null && node.right == null check; if the only check is done for node == null, cases will be missed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

https://leetcode.com/problems/construct-string-from-binary-tree/

code

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

https://leetcode.com/problems/insert-into-a-binary-search-tree/description/

don’t code but must review logic

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

https://leetcode.com/problems/delete-node-in-a-bst/description/

code and review logic!!

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

https://leetcode.com/problems/count-good-nodes-in-binary-tree/

don’t code but must review logic

A

helper function takes in node, info, and greatestVal.

if node.val >= greatestVal, update info.

update greatestVal accordingly.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

https://leetcode.com/problems/validate-binary-search-tree/description/

don’t code but must review logic

A

create a helper function. must pass in min valid value and max valid value into it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

code!!

A

.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

code and review logic

A

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

17
Q

https://leetcode.com/problems/unique-binary-search-trees/

code helper func only, and review logic

A

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)

18
Q

https://leetcode.com/problems/sum-root-to-leaf-numbers/description/

don’t code but must review logic

A

use global var sum.
pass an int ‘path’ into the helper function. path = 10 * path + node.val.

19
Q

https://leetcode.com/problems/house-robber-iii/description/

code and review logic

A

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];

20
Q

https://leetcode.com/problems/flip-equivalent-binary-trees/description/

don’t code; review logic of return stmt only

A

.

21
Q

https://leetcode.com/problems/all-possible-full-binary-trees/description/

code and review logic

A
  • 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]
22
Q

https://leetcode.com/problems/trim-a-binary-search-tree/description/

code and review logic

A

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

23
Q

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/description/

don’t code but must review logic

A

must use gloval var for sum

review code

24
Q

https://leetcode.com/problems/binary-search-tree-iterator/description/

code and review logic

A

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

25
Q

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/

code and review logic

A

PRE order traversal

use global var for index.

split serialized string at commas.

26
Q

https://leetcode.com/problems/binary-tree-maximum-path-sum/

code and review logic

A

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.

27
Q

reverse LL iterative and recursive

code

A

.

28
Q

https://leetcode.com/problems/palindrome-linked-list/description/

don’t code; review logic

A

at the beginning, must include

if (head == null || head.next == null) return true;

29
Q

https://leetcode.com/problems/remove-linked-list-elements/description/

don’t code; review logic

A

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

30
Q

https://leetcode.com/problems/intersection-of-two-linked-lists/description/

code again

A

.

31
Q

https://leetcode.com/problems/reorder-list/description/

don’t code; review logic

A
  1. reverse list starting from mid. then it becomes clear how to merge
  2. review order of reassigning and advancing pointers
  3. handle case of odd length list
32
Q

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

don’t code; review logic

A

advance fast ptr n times (while fast is not null and n– > 0). use dummy head to avoid handling edge cases.

33
Q

https://leetcode.com/problems/check-completeness-of-a-binary-tree/description/

A

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

34
Q

https://leetcode.com/problems/maximum-width-of-binary-tree/

A

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

35
Q

https://leetcode.com/problems/convert-bst-to-greater-tree/description/

A

sum must be in Info class

36
Q

https://leetcode.com/problems/find-duplicate-subtrees/description/

A

serialization = cur.val + “,” + postorder(cur.left, map, res) + “,” + postorder(cur.right, map, res);

return this serialization in the helper function

37
Q

https://leetcode.com/problems/minimum-distance-between-bst-nodes/description/

review logic

A

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

38
Q

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

A

bfs. to insert right to left:
level.add(0, node.val);