Tree
[1]:
import IPython; IPython.display.HTML('''<script>code_show=true; function code_toggle() { if (code_show){ $('div.nbinput').show(); } else { $('div.nbinput').hide(); } code_show = !code_show} $( document ).ready(code_toggle);</script><form action="javascript:code_toggle()"><input type="submit" value="Click here to toggle on/off the raw code."></form>''')
[1]:
94. Binary Tree Inorder Traversal
Easy
Given the root of a binary tree, return the inorder traversal of its nodes’ values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]
Constraints:
The number of 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?
[1]:
# recursion
def inorderTraversal(root):
if not root:
return []
else:
return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)
100. Same Tree
Easy
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Constraints:
The number of nodes in both trees is in the range [0, 100].
-10^4 <= Node.val <= 10^4
[1]:
# recursion
def isSameTree(p, q):
if p is None and q is None:
return True
elif p or q:
return False
else:
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right) and (p.val == q.val)
102. Binary Tree Level Order Traversal
Medium
Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Constraints:
The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000
[ ]:
# BFS
from collections import deque
def levelOrder(root):
q = deque()
if root:
q.append(root)
res = []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(level)
return res
814. Binary Tree Pruning
Medium
Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.
A subtree of a node node is node plus every node that is a descendant of node.
Example 1:
Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation:
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.
Constraints:
The number of nodes in the tree is in the range [1, 200].
Node.val is either 0 or 1.
[ ]:
# recursion
def pruneTree(root):
if not root:
return None
root.left = pruneTree(root.left)
root.right = pruneTree(root.right)
if root.val==0 and (not root.left) and (not root.right):
return None
else:
return root
112. Path Sum
Easy
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
Constraints:
The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
[1]:
# recursion
def hasPathSum(root, targetSum):
if not root:
return False
if (not root.left) and (not root.right):
return targetSum == root.val
else:
return hasPathSum(root.left, targetSum-root.val) or hasPathSum(root.right, targetSum-root.val)
129. Sum Root to Leaf Numbers
Medium
You are given the root of a binary tree containing digits from 0 to 9 only.
Each root-to-leaf path in the tree represents a number.
For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.
A leaf node is a node with no children.
Example 1:
Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
Constraints:
The number of nodes in the tree is in the range [1, 1000].
0 <= Node.val <= 9
The depth of the tree will not exceed 10.
[ ]:
# recursively returns list of strings like ['12', '13'] and sum them in the end
def numbers(root):
'''
Returns a list of strings, for example ['12', '13'].
'''
if (not root.left) and (not root.right):
return [str(root.val)]
else:
res = []
if root and root.left:
res += [str(root.val) + num for num in self.numbers(root.left)]
if root and root.right:
res += [str(root.val) + num for num in self.numbers(root.right)]
return res
def sumNumbers(root):
return sum(int(num) for num in numbers(root))
[ ]:
# DFS compute sum given current sum
def dfs(self, root, cur_sum):
if not root: # tree [0, 1] will break without this
return 0
cur_sum = 10*cur_sum + root.val
if (not root.left) and (not root.right):
return cur_sum
sum_l = dfs(root.left, cur_sum)
sum_r = dfs(root.right, cur_sum)
return sum_l + sum_r
def sumNumbers(root):
return dfs(root, 0)
236. Lowest Common Ancestor of a Binary Tree
Medium
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Constraints:
The number of nodes in the tree is in the range [2, 10^5].
-10^9 <= Node.val <= 10^9
All Node.val are unique.
p != q
p and q will exist in the tree.
[1]:
# LeetCode 上最快解答：DFS 從下向上（divide and conquer 先遞迴傳回結果再合併）
def lowestCommonAncestor(root, p, q):
if root in [p, q, None]:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
elif left:
return left
else:
return right
508. Most Frequent Subtree Sum
Medium
Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.
The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).
Example 1:
Input: root = [5,2,-3]
Output: [2,-3,4]
Constraints:
The number of nodes in the tree is in the range [1, 10^4].
-10^5 <= Node.val <= 10^5
[ ]:
from collections import defaultdict
def findFrequentTreeSum(root):
'''
We need to know the the sum at each node and keep a counter.
'''
freq = defaultdict(int)
def dfs(node):
if not node:
return 0
else:
subtree_sum = node.val + dfs(node.left) + dfs(node.right)
freq[subtree_sum] += 1
return subtree_sum
dfs(root)
max_freq = max(freq.values())
return [s for s, f in freq.items() if freq[s]==max_freq]
[3]:
# my ugly solution -- compute tree of subtree sum first
from collections import defaultdict
def findFrequentTreeSum(root):
sums = serialize(tree_sum(root))
freq = defaultdict(int)
for s in sums:
freq[s] += 1
max_freq = max(freq.values())
return [s for s, f in freq.items() if f==max_freq]
def serialize(root):
if not root:
return []
return serialize(root.left) + [root.val] + serialize(root.right)
def tree_sum(root):
if (not root) or ((not root.left) and (not root.right)):
return root
left = tree_sum(root.left)
right = tree_sum(root.right)
root.val += ((left.val if left else 0) + (right.val if right else 0))
root.left = left
root.right = right
return root