Tree Flashcards
- Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1 / \ 2 2 / \ / \ 3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1 / \ 2 2 \ \ 3 3
Follow up: Solve it both recursively and iteratively.
Recursive or Iterative.
The basic idea is compare node.left with node.right
node.right with node.left.
Recursive version is much easy.
Iterative version need to 巧妙的append node到queue裡面
- Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root: return []
q = [root]
out = []
while q:
length = len(q)
node_list = []
for i in xrange(len(q)):
cur = q.pop(0)
node_list.append(cur.val)
if cur.left: q.append(cur.left)
if cur.right: q.append(cur.right)
out.append(node_list)
return out
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
queue, res, level = [], [], 0
queue.append((level, root))
while(queue):
level, cur = queue.pop(0)
if len(res) == level:
res.append([])
res[level].append(cur.val)
if cur.left: queue.append((level+1, cur.left))
if cur.right: queue.append((level+1, cur.right))
return res
- Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]
這題不難
正常的BFS，只是在存output的時候，不要想用append的，先init好list大小，把值 直接放到想放的index
BFS
while + for寫法
init queue
while q
for q
cur=q.pop(0)
if cur.left: q.append(cur.left)
if cur.right: q.append(cur.right)
while and save (level, node)
inti q
while q
if cur.left: queue.append((level+1, cur.left))
if cur.right: queue.append((level+1, cur.right))
- Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:
2 / \ 1 3
Input: [2,1,3]
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node’s value is 5 but its right child’s value is 4.
- use recursive. input upper bound and lower bound. And check the root.val always between upper and lower
- use iterative inorder traversal. If the val always become larger. it is valid
- Binary Tree Preorder Traversal
Given the root of a binary tree, return the preorder traversal of its nodes’ values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,2,3]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Example 4:
Input: root = [1,2]
Output: [1,2]
Example 5:
Input: root = [1,null,2]
Output: [1,2]
Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
recursive
iterative
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
out = []
stack = []
cur = root
while stack or cur:
if cur:
stack.append(cur)
out.append(cur.val) # write the first look node
cur = cur.left
else:
node = stack.pop()
cur = node.right
return out
- Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes’ values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
~~~
Output: [1,3,2]
~~~
Follow up: Recursive solution is trivial, could you do it iteratively?
recursive
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
def inorder(cur):
if not cur:
return
inorder(cur.left)
res.append(cur.val)
inorder(cur.right)
inorder(root)
return res
iterative
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
out = []
stack = []
cur = root
while stack or cur:
if cur:
stack.append(cur)
cur = cur.left
else:
node = stack.pop()
out.append(node.val) # write the pop node in the stack # 在cur=cur.left, cur=cur.right之間 write
cur = node.right
return out
- Binary Tree Postorder Traversal
Given the root of a binary tree, return the postorder traversal of its nodes’ values.
Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Example 4:
Input: root = [1,2]
Output: [2,1]
Example 5:
Input: root = [1,null,2]
Output: [2,1]
Constraints:
The number of the nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
Follow up:
Recursive solution is trivial, could you do it iteratively?
recursive
iterative
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
cur, stack = root, []
res = []
while(stack or cur):
if cur:
stack.append((cur, False))
cur = cur.left
else:
cur, visited = stack[-1]
if visited:
stack.pop()
res.append(cur.val)
cur = None #關鍵，因為root被去掉了，應該要再回上一個root，但現在cur是這個root，
#下個迴圈cur not None，他又會在cur = cur.left沒完沒了，
#所以這邊要刻意cur = None，讓他繼續在cur is None這邊，
#他就會再從stack拿上一個root出來
else:
stack[-1] = (cur, True)
cur = cur.right
#print(stack)
return res
Memorize
常用功能
1. preorder
Iterative
Recursive
- inorder
Iterative
Recursive
- postorder
Iterative
Recursive
- level order
Iterative
Recursive
常見bug
1. cur= cur.left when cur.left is None
2. 空樹
if not root:
return
3. none children
if node.left and xxxx
if node.right and xxxx
常用trick
- Delete Nodes And Return Forest
Given the root of a binary tree, each node in the tree has a distinct value.
After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).
Return the roots of the trees in the remaining forest. You may return the result in any order.
Example 1:
Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]
Constraints:
The number of nodes in the given tree is at most 1000.
Each node has a distinct value between 1 and 1000.
to_delete.length <= 1000
to_delete contains distinct values between 1 and 1000.
DFS 去traverse，只有當自己不在to_delete，且自己是root的時候在insert進答案。
然後用dfs 把left right 繼續算。並且最後，如果left, right如果在to_delete，那就要把node.left = None
- Path Sum III
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
- 5 -> 3
- 5 -> 2 -> 1
- -3 -> 11
O(N^2)
這題先想簡單的題目，如果path一定是從root開始的話怎麼做。然後這題就是用這個function去兜出來，DFS到一個node，你就分成兩部分，一個是是否start with this node as root，或是不要。
但還有一個問題，當你的parent已經involed進去，那你一定也要involved，不然就算你最後有找到符合的sum，這個path也是斷掉的
O(N)
- Count Complete Tree Nodes
Given a complete binary tree, count the number of nodes.
Note:
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Example:
Input:
1
/ \
2 3
/ \ /
4 5 6
~~~
Output: 6
先找最左高度，在找最又高度，如果一樣就表示這是perfect binary Tree，這樣就可直接算數量，如果不一樣，就分左右再遞迴這個function。
- Flip Equivalent Binary Trees
For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.
A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.
Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivelent or false otherwise.
Example 1:
Flipped Trees Diagram
Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Explanation: We flipped at nodes with values 1, 3, and 5.
Example 2:
Input: root1 = [], root2 = []
Output: true
Example 3:
Input: root1 = [], root2 = [1]
Output: false
Example 4:
Input: root1 = [0,null,1], root2 = []
Output: false
Example 5:
Input: root1 = [0,null,1], root2 = [0,1]
Output: true
Constraints:
The number of nodes in each tree is in the range [0, 100].
Each tree will have unique node values in the range [0, 99].
只要比較root node，不管left right長怎樣就是先跑recursive，到下一層的root會自己看自己相不相同回傳true false.
- Vertical Order Traversal of a Binary Tree
Given a binary tree, return the vertical order traversal of its nodes values.
For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).
Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).
If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.
Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.
Example 1:
Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).
Example 2:
Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report “[1,5,6]”, the node value of 5 comes first since 5 is smaller than 6.
Note:
The tree will have between 1 and 1000 nodes.
Each node’s value will be between 0 and 1000.
其實很簡單，traverse一次，記錄所有需要的資料，然後把資料用排序整理，轉乘output
