Binary Tree
4 min readDec 18, 2019
The binary tree problems usually can be solved by using recursion.
894. All Possible Full Binary Trees
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from functools import lru_cache
class Solution:
def allPossibleFBT(self, N: int) -> List[TreeNode]:
@lru_cache(None)
def helper(n):
if n==1:
return [TreeNode(0)]
elif n%2==0:return []
else:
res = []
for i in range(1, n):
left=helper(i)
right = helper(n-1-i)
if left and right:
for l in left:
for r in right:
node = TreeNode(0)
node.left = l
node.right = r
res.append(node)
return res
return helper(N)872. Leaf-Similar Trees
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:
def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
self.res = []
def helper(node):
if node is None:return
if node.left is None and node.right is None:
self.res.append(node.val)
else:
helper(node.left)
#helper(node)
helper(node.right)
helper(root1)
res1 = self.res[:]
self.res = []
helper(root2)
return res1 == self.res
865. Smallest Subtree with all the Deepest Nodes
https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/
My ugly workable code (36ms)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:
def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
depth =collections.defaultdict(list)
parents = {root.val:-1}
val_node = collections.defaultdict(list)
def helper(parent, node, d):
if node is None:
return
else:
val_node[node.val] =[node, d]
depth[d].append(node.val)
if parent is not None:
parents[node.val]= parent.val
helper(node, node.left, d+1)
helper(node, node.right, d+1)
helper(None, root, 0)
max_d = max(depth.keys())
paths = []
for val in depth[max_d]:
this_path = [val]
while True:
if parents[val]!=-1:
val = parents[val]
this_path.append(val)
else:
break
paths.append(this_path)
common = set(paths[0])
for p in paths[1:]:
common &= set(p)
fin_res = [val_node[v] for v in common]
fin_res,_ = max(fin_res, key=lambda x:x[1])
return fin_res
More elegant code can be found here:
863. All Nodes Distance K in Binary Tree
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/
recusion and BFS
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
if k==0:return [target.val]
parent = {}
def helper(nodea, nodeb):
if nodeb is not None:
parent[nodeb.val] = nodea
helper(nodeb, nodeb.left)
helper(nodeb, nodeb.right)
helper(root, root.left)
helper(root, root.right)
def bfs(node):
res = []
from collections import deque
Q = deque([(target, 0)])
seen = {target.val}
while Q:
node, d = Q.popleft()
for child_node in [node.left, node.right, parent[node.val] if node.val in parent else None]:
if child_node is not None and child_node.val not in seen and d+1<=k:
seen.add(child_node.val)
if d+1==k:res.append(child_node.val)
elif d+1<k:
Q.append((child_node, d+1))
return res
return bfs(target)
1325. Delete Leaves With a Given Value
My naive solution
class Solution:
def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode:
nodes, parents = [], {}
def helper(node, parent, lr):
if node is None:return
if node.val==target:
nodes.append(node)
parents[node]=(parent,lr)
helper(node.left, node, 'left')
helper(node.right, node, 'right')
helper(root, None, 'left')
while True:
removed, new_nodes = False, []
for node in nodes:
parent_node, direction = parents[node]
if node.left is None and node.right is None:
if parent_node is None:return None
removed = True
if direction == 'left':parent_node.left = None
else:parent_node.right = None
else:
new_nodes.append(node)
nodes = new_nodes[:]
if not removed:return rootWe can have a shorter version
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:
def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode:
if root.left: root.left = self.removeLeafNodes(root.left, target)
if root.right: root.right = self.removeLeafNodes(root.right, target)
return None if root.left == root.right and root.val == target else root
1343. Maximum Product of Splitted Binary Tree
https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/
C++
class Solution {
public:
vector<int> d;
int helper(TreeNode* node) {
if (node==nullptr) return 0;
int left = helper(node->left), right = helper(node->right);
d.push_back(left);d.push_back(right);
return left+right+node->val;
}
int maxProduct(TreeNode* root) {
int sum = helper(root);
long long res = 0;
for (auto i:d) res = max(res, (long long)i*(sum-i));
return res % int(1e9+7);
}
};Runtime: 172 ms, faster than 100.00% of C++ online submissions for Maximum Product of Splitted Binary Tree.Memory Usage: 73.2 MB, less than 100.00% of C++ online submissions for Maximum Product of Splitted Binary Tree.
Python
class Solution:
def maxProduct(self, root: TreeNode) -> int:
d = []
def helper(node):
if node is None:return 0
left = helper(node.left)
right = helper(node.right)
d.extend([left,right])
return left+right+node.val
S = helper(root)
res = max(i*(S-i) for i in d)
return res %(10**9+7)Runtime: 316 msMemory Usage: 78.3 MB
