Solving Tree Problems on LeetCode
Part of this great node comes from blog:
Outline
- DFS Traverse Binary Tree
- Preorder traverse Recusive
- Preorder traverse iterative
- Preorder divide and conquer
2. Traverse Method and Divide and Conquer
- Maximum Depth of Binary Tree
- Balanced Binary Tree
3. The maximum path sum of BT (root->leaf)
- Binary Tree Maximum Path Sum II (root->any)
- Binary Tree Maximum Path Sum (any->any)
- Binary Tree Maximum Path Sum (any->any) with negative value
4. Binary Search Tree
- Validate Binary Search Tree
- Binary Search Tree Iterator
- Construct BST
- Find Element in BST
- Trim BST
- Split BST
5. Binary Search Tree level by level
- Binary Tree Level-Order Traversal
Basic
construct a TreeNode structure
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None1. DFS Traverse Binary Tree
1.1 Preorder traverse：
vector<int> res;
void helper(TreeNode* root) {
if (!root) return;
res.push_back(root->val);
if (root->left) {
helper(root->left);
}
if (root->right) {
helper(root->right);
}
}
vector<int> preorderTraversal(TreeNode *root) {
if (!root) {
return res;
}
helper(root);
return res;
}1.2 Divide and Conquer to implement Preorder Traverse：
To make it easier to understand, the queue has a target, then we assign it to two workers A and B to collect the result from left subtree and the right subtree, which we get A=[2,4,5], B=[3]. Then the final result = the result of the queue + left + right = [1,2,4,5,3].
vector<int>preorderTraversal(TreeNode *root) {
vector<int> res;
if (!root) {
return res;
}
//Divide, no need to check if the left exist or not
vector<int> left = preorderTraversal(root->left);
vector<int> right = preorderTraversal(root->right);
//Conquer
res.push_back(root->val);//current, left, right
res.insert(res.end(), left.begin(), left.end());
res.insert(res.end(), right.begin(), right.end());
return res;
}1.3 Iterative Preorder traverse：
For this way, because traverse is a DFS method, which makes us think about using stack to save the result. Note: because the stack is FILO, if we want to visit left subtree at first, we need to push the right subtree at first. This iterative implementation is better than the recursive version, because the memory we use here is the heap memory = memory size. While for the recursive version, it uses the stack memory = processing memory, so it is easier to run out of memory.
vector<int> preorderTraversal(TreeNode *root) {
vector<int> res;
if (!root) {
return res;
}
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* tmp = s.top();
s.pop();
res.push_back(tmp->val);
// 这里注意：栈是先进后出，所以先push右子树
if (tmp->right) {
s.push(tmp->right);
}
if (tmp->left) {
s.push(tmp->left);
}
}
return res;
}2. Traverse VS Divide and Conquer
In this section I will include examples to illustrate how to use traverse and what does it mean with divide and conquer.
2.1 Maximum Depth of Binary Tree
http://www.lintcode.com/zh-cn/problem/maximum-depth-of-binary-tree/
Given a binary tree, find the maximum depth which is defined as the longest distance from root node to leaves.
Example
1
/ \
2 3
/ \
4 5The depth of this binary tree is 3
Solution: the conventional way is to use the preorder, it is DFS, so that we need to use a global variable to save the maximum height. However, it is a lot easier to use divide and conquer to do it, we get the left and right height, then we use max(left,right)+1 to combine the result. Also, we can use BFS level-by-level to traverse and get the maximum height of the last level.
2.2 Balanced Binary Tree
http://www.lintcode.com/zh-cn/problem/balanced-binary-tree/
Given a BT, we need to validate that it is a balanced binary tree. Definition of balanced binary tree: if for every node in a given BT, the difference of the depth of its left subtree and right subtree will not be larger than 1.
Example
Given BT A=
{3,9,20,#,#,15,7}, B={3,#,20,15,7}
A) 3 B) 3
/ \ \
9 20 20
/ \ / \
15 7 15 7A is a balanced BT，B is not
We just need to see the difference of the height of left subtree and the right subree>1: return False. return (True, 0) for the base case.
2.3 Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.
2.4 Minimum Subtree
Given a binary tree, find the subtree with minimum sum. Return the root of the subtree.
LintCode will print the subtree which root is your return node.
Solution: we need to get the value of the whole tree, = helper(left)+helper(right)+current val. It’s guaranteed that there is only one subtree with minimum sum and the given binary tree is not an empty tree.
2.5 The maximum path sum in BT
（1）the maximum path sum（root->leaf）
Example:
For the following BT：
1
/ \
2 3
Return 4。(The maximum path is 1→3)
However, if we have negative value, this is not going to work
public int maxPathSum2(TreeNode root) {
if (root == null) {
return 0 #th
}
int left = maxPathSum2(root.left)
int right = maxPathSum2(root.right)
return root.val + Math.max(left, right) #at least root+one of the subtree
}（2）the maximum path sum（root->any）
Binary Tree Maximum Path Sum II
http://www.lintcode.com/zh-cn/problem/binary-tree-maximum-path-sum-ii/
The path can be from root to any node, but it needs include at least one nod, which is the root.
Example
For the following BT：
1
/ \
2 3
Return 4。(Maximum Path为1→3)
Solution: this one is slightly different, for each node, we can return the sum of current node +left subtree, or current node+ right subtree, or we just return current node, which means the path ends here.
For the divide and conquer：
1.Recursive end consition：when the node is null
2.Divide：divide the tree into the result of the left subtree and right subtree
3.Conquer：merge the result from the divide.
public int maxPathSum2(TreeNode root) {
if (root == null) {
return 0;
}
//divide
int left = maxPathSum2(root.left);
int right = maxPathSum2(root.right); //conquer
return root.val + Math.max(0, Math.max(left, right)); #if the max is negative, we get rid of them, use 0 instead.
}
（3）the maximum path sum（any->any）
2.5 Binary Tree Maximum Path Sum
124. Binary Tree Maximum Path Sum
Given a BT, find a the path with maximum sum, this path can start from any node and end at any node.
Example
Given a BT：
1
/ \
2 3
Return6
Solution: The difference compared with before is the result is not the current value plus either the left, or the right, or 0, it is the maximum sum of these (except for the current node, the left, the right we only add if it is larger than 0), which equals to max(val, val+left, val+right,left+val+right,val). Also, in this process, we need a global variable to save the maximum value.
from sys import maxsize
class Solution:
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
maxv = -maxsize
def helper(root): #return max from current root to any node
nonlocal maxv
if not root:
return 0
tmp =root.val
left = helper(root.left)
right = helper(root.right)
if left>0:
tmp+=left
if right>0:
tmp+=right
maxv=max(maxv,tmp)
return max(0,max(left,right))+root.valif not root:
return 0
helper(root)
return maxv
3. Reverse from Traverse result to build tree
105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]Return the following binary tree:
3
/ \
9 20
/ \
15 7Solution: we use divide and conquer, first find the current node as the first node in preorder, and then cut the inorder into two halves beside the current node. According to the result to separate the preorder into two halves.
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
#first to decide the root
def helper(preorder,inorder):
if not preorder or not inorder:
return None
cur_val = preorder[0]
node = TreeNode(cur_val)
#divide: now cut the lists into two halfs
leftinorder,rightinorder = [],[]
bLeft=True
for e in inorder:
if e==cur_val:
bLeft=False #switch to the right side
continue
if bLeft:
leftinorder.append(e)
else:
rightinorder.append(e)
leftset, rightset = set(leftinorder),set(rightinorder)
leftpreorder, rightpreorder = [],[]
for e in preorder[1:]:
if e in leftset:
leftpreorder.append(e)
else:
rightpreorder.append(e)
#conquer
node.left=helper(leftpreorder, leftinorder)
node.right= helper(rightpreorder,rightinorder)
return node
return helper(preorder,inorder)However, the previous code has problem as 203 / 203 test cases passed.
Status: Memory Limit Exceeded. So instead of passing new array, I use index.
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
#first to decide the root
def helper(pre_l, pre_r,in_l, in_r): #[pre_l,pre_r)
if pre_l>=pre_r or in_l>=in_r:
return None
cur_val = preorder[pre_l]
node = TreeNode(cur_val)
#divide: now cut the lists into two halfs
leftinorder = set()
inorder_index = -1
for i in range(in_l, in_r):
if inorder[i]==cur_val:
inorder_index = i
break
leftinorder.add(inorder[i])
#when leftset is empty
new_pre_r=pre_l
for i in range(pre_l+1,pre_r):
if preorder[i] in leftinorder:
new_pre_r = i
else:
break
new_pre_r+=1
#conquer
node.left=helper(pre_l+1, new_pre_r, in_l, inorder_index)
node.right= helper(new_pre_r,pre_r, inorder_index+1, in_r)
return node
if not preorder or not inorder:
return None
return helper(0,len(preorder),0,len(inorder))4. Time complexity of Binary Tree
If we spent O(n) to convert T(n) to 2T(n/2)
T(n) = 2T(n/2) + O(n)
= 2 * 2T(n/4) + O(n) + O(n)
=nlogn (the same as merge sort)
If it is O(1)
T(n) = 2T(n/2) + O(1)
= 2 * 2T(n/4) + O(1) + O(1)
=n + (1 + 2 + 4 +…+ n)
≈n + 2n
≈O(n)
Binary Search Tree(BST)
Binary Search Tree : Insert / Remove / Find / Validate
Definition and Features
F1: For a BST, the left subtree are all smaller than the current node, and the right subtree are all bigger than the current node. This concept is useful in trimming BST, see example,669. Trim a Binary Search Tree.
- t.successor(x) is the smallest item in t that is strictly greater than x, null if there is no such node. Also called in-order successor, which is the next node in Inorder traversal of the Binary Tree. e.g. for node 14, successor(14)=15 = min(14.right), successor(15)=18, where right does not exist, then it is the parent
def inOrderSuccessor(root, n):
# Step 1 of the above algorithm
if n.right is not None:
return minValue(n.right)
# Step 2 of the above algorithm
p = n.parent
while( p is not None):
if n != p.right :# if current node is the left node, then break
break
n = p
p = p.parentreturn p
- t.predecessor(x) is the largest item in t that is strictly smaller than x, null if there is no such node. e.g. for node 14, predecessor(14)=12= max(14.left)
- LCA: The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).” e.g., if u=5,w=19, then we first node when we recursively visiting the tree that is within [u,w], then the LCA is 14.
- In order traverse can be used to sorting. e.g. 230. Kth Smallest Element in a BST
- Smallest and the Biggest Value
#recursive
def getSmallest(node):
if not node:
return None
if node.left:
return getSmallest(node.left)
return node
#iterative
def getSmallest(node):
while node:
node=node.left
return node2. Common Solution
For this type of trees, the most common way is to do it recursively with BFS or DFS. Or sometimes, if we just need to find an element, we can use WHILE to do it iteratively.
Steps to solve the problem:
Get a toy example: need to be big enough to almost include all the cases.
If the problem is simple and standard: do DFS (inorder,pre-order, post-oder) traverse (recursively is easier), or BFS (level-by-level) traverse (iteratively is easier). The standard here means we can get the answer just by traversing elements with the standard definition.
If the problem is simple but not standard: we can use while loop to traverse the subtree which satisfies the condition and can potentially lead us to the solution. Here, get a toy example is very important.
4. If the problem is harder and which asks us to manipulate the tree, e.g. trimming, splitting, using recursive method which return node. Firstly, get the end condition, return None or (None,None). Second, traverse the tree according to the requirement, and return node. Third, rearrange the node, node.left,node.right and return
def RecursiveReturnNode(root):
#First
if not root:
return None
# second
if root.val is condition 1:
node =RecursiveReturnNode(node.left)
node.left manipulation
node.right manipulation
return node if root.val is condition 2:
RecursiveReturnNode(node.left)
node.left manipulation
node.right manipulation
2.1 Generate BST
single tree from an array: 108. Convert Sorted Array to Binary Search Tree , all possible tree: 96. Unique Binary Search Trees
108. Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9],One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:0
/ \
-3 9
/ /
-10 5
Solution: use the binary search algorithm, the stop condition is when the l>r.
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
def generatebalancedBST(l,r):
if l>r:
return None
m = (l+r)//2
tree = TreeNode(nums[m])
tree.left = generatebalancedBST(l,m-1)
tree.right = generatebalancedBST(m+1,r)
return tree
return generatebalancedBST(0,len(nums)-1)109. Convert Sorted List to Binary Search Tree, the difference is here we have a linked list, we can convert the linked list into a list nums
96. Unique Binary Search Trees
Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3Solution: When we read the signal, list all of it, we need to use for loop, to pose each element as root, and the left side is left tree, the right side is used for the right tree. Use DPS: We generated all the BST that use ith node as root
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
def constructAllBST(start,end):
if start>end:
return [None]
#go through the start to end, and use the ith as root
rslt=[]
leftsubs,rightsubs=[],[]
for i in xrange(start,end+1):
leftsubs=constructAllBST(start,i-1)
rightsubs=constructAllBST(i+1,end)
for leftnode in leftsubs:
for rightnode in rightsubs:
node = TreeNode(i)
node.left=leftnode
node.right=rightnode
rslt.append(node)
return rsltrslt= constructAllBST(1,n)
return len(rslt)
If we only need length, a slightly better solution showing as follows.
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
def constructAllBST(start,end):
if start>end:
return 1
#go through the start to end, and use the ith as root
count = 0
leftsubs,rightsubs=[],[]
for i in xrange(start,end+1):
leftsubs=constructAllBST(start,i-1)
rightsubs=constructAllBST(i+1,end)
count+=leftsubs*rightsubs
return countrslt= constructAllBST(1,n)
return rslt
However, it still cant pass the test, try the bottom up iterative solution with memorization: T(start,end)=T(start,i-1)*T(i+1,end) T(j,i)=T(j,i-1)*T(i+1,i). How to explain this?
def numTrees1(self, n):
res = [0] * (n+1)
res[0] = 1
for i in xrange(1, n+1): #when i=2, j=[0,1] res[2] = res[0]*res[2-1-0] + res[1]*res[2-1-1]
for j in xrange(i): #i [1,n], j =[0,i), the case if for one node,
res[i] += res[j] * res[i-1-j]
return res[n]Using math:
# Catalan Number (2n)!/((n+1)!*n!)
def numTrees(self, n):
return math.factorial(2*n)/(math.factorial(n)*math.factorial(n+1))2.2 Find certain element of the tree:
successor or predecessor:285. Inorder Successor in BST, 235. Lowest Common Ancestor of a Binary Search Tree
285. Inorder Successor in BST
First, we can follow the definition, use the inorder traverse to get a list of the whole nodes, and we search for the node p and return its next in the lst.
#takes 236 ms
def inorderSuccessor(self, root, p):
"""
:type root: TreeNode
:type p: TreeNode
:rtype: TreeNode
"""
lst = []
def inorderTravel(node):
if not node:
return None
inorderTravel(node.left)
lst.append(node)
inorderTravel(node.right) inorderTravel(root)
for i in xrange(len(lst)):
if lst[i].val==p.val:
if i+1<len(lst):
return lst[i+1]
else:
return None
However, the definition takes O(N+N), also space complexity is O(N). A slightly better version is when we traverse to find this node, the successor is the last bigger value. So we keep recording the succ
#takes 108ms
def inorderSuccessor(self, root, p):
"""
:type root: TreeNode
:type p: TreeNode
:rtype: TreeNode
"""
#find min(p.right)
succ = None
while root:
if p.val < root.val: #node is bigger than p, go to left
succ = root #it might be the successor since its bigger
root = root.left
else: #node has the same value or smaller value than p, go to right
root = root.right
return succ235. Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Solution: we traverse the tree to find the first element that is in the range.
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
s=min(p.val,q.val)
b=max(p.val,q.val)
def LCA(node):
if not node:
return None
if node.val>b:
return LCA(node.left)
if node.val<s:
return LCA(node.right)
return node
return LCA(root)230. Kth Smallest Element in a BST
Solution: Here, DFS-inorder-recursive; if we use python, then we need to use list as global variable
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
count = [k] #use list to function as global variable
num=[-1]
#inorder traversal
def inorder(node):
if node.left:
inorder(node.left)
count[0]-=1 #visit
if count[0]==0:
num[0]=node.val
return
if node.right:
inorder(node.right)
inorder(root)
return num[0]Second: DFS iterative
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
count = k
num=-1
#DFS iterative
#1: add all the left nodes
while root:
stack.append(root)
root=root.left
#visit stack, if node.right exist, then add in the stack
while stack:
node=stack.pop()
count-=1
if count==0:
return node.val
#check if the right exist
right=node.right
while right:
stack.append(right)
right=right.left #keep getting the successor270. Closest Binary Search Tree Value
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
Note:
- Given target value is a floating point.
- You are guaranteed to have only one unique value in the BST that is closest to the target.
from sys import maxint
class Solution:
def closestValue(self, root, target):
"""
:type root: TreeNode
:type target: float
:rtype: int
"""
mind= maxint #current smallest
rslt= -1
while root:
if root.val>target:
if root.val-target<mind:
mind = root.val-target
rslt=root.val
root=root.left
elif root.val<target:
if target-root.val<mind:
mind = target - root.val
rslt=root.val
root=root.right
else:
return root.val
return rslt272. Closest Binary Search Tree Value II
2.3 Trim the tree
maybe with value in the range: 669. Trim a Binary Search Tree
669. Trim a Binary Search Tree
Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Example 1:
Example 2:Input:
3
/ \
0 4
\
2
/
1 L = 1
R = 3Output:
3
/
2
/
1
Solution: Based on F1, if the value of current node is smaller than L, suppose at 0, then we delete its left child, node.left = None, then we check its right size, go to node.right, we return node = goto(node.right), if it is within range, then we keep checking left, right, and return current node
def trimBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""
def trimUtil(node):
if not node:
return None
if node.val<L:
node.left=None #cut the left, the left subtree is definitly smaller than L
node =trimUtil(node.right) #node = node.right #check the right
return node
elif node.val>R:
node.right=None
node=trimUtil(node.left)
return node
else:
node.left=trimUtil(node.left)
node.right=trimUtil(node.right)
return node
return trimUtil(root)A mutant of this is to split the BST into two, one is smaller or equal to the given value, the other is bigger.
2.4 Split the tree
with a certain value ,776. Split BST
Given a Binary Search Tree (BST) with root node root, and a target value V, split the tree into two subtrees where one subtree has nodes that are all smaller or equal to the target value, while the other subtree has all nodes that are greater than the target value. It's not necessarily the case that the tree contains a node with value V.
Additionally, most of the structure of the original tree should remain. Formally, for any child C with parent P in the original tree, if they are both in the same subtree after the split, then node C should still have the parent P.
You should output the root TreeNode of both subtrees after splitting, in any order.
Example 1:
Input: root = [4,2,6,1,3,5,7], V = 2
Output: [[2,1],[4,3,6,null,null,5,7]]
Explanation:
Note that root, output[0], and output[1] are TreeNode objects, not arrays.The given tree [4,2,6,1,3,5,7] is represented by the following diagram:4
/ \
2 6
/ \ / \
1 3 5 7
Solution: The coding is quite similar as the trimming.
class Solution(object):
def splitBST(self, root, V):
"""
:type root: TreeNode
:type V: int
:rtype: List[TreeNode]
"""
def splitUtil(node):
if not node:
return (None,None)
if node.val<=V:
sb1,sb2 = splitUtil(node.right) #the left subtree will satisfy the condition, split the right subtree
node.right=sb1 #Now set the right subtree with sb1 that
return (node, sb2)
else:
sb1, sb2=splitUtil(node.left) #the right subtree satisfy the condition, split the left subtree
node.left=sb2
return (sb1,node)
return list(splitUtil(root))
