Nail Your Next Job Interview - Tree

Tree Structure

101. Symmetric Tree [x]

https://leetcode.com/problems/symmetric-tree/description/

iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.add(root.left);
q.add(root.right);
while (!q.isEmpty()) {
TreeNode t1 = q.poll();
TreeNode t2 = q.poll();
if (t1 == null && t2 == null) continue;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
q.add(t1.left);
q.add(t2.right);
q.add(t1.right);
q.add(t2.left);
}
return true;
}
}

recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public boolean isSymmetric(TreeNode root) {
return root == null || checkSymmetric(root.left, root.right);
}
public boolean checkSymmetric(TreeNode left, TreeNode right) {
if (left == null || right == null) {
return left == right;
}
if (left.val != right.val) {
return false;
}
return checkSymmetric(left.left, right.right) && checkSymmetric(left.right, right.left);
}
}

100. Same Tree [x]

https://leetcode.com/problems/same-tree/description/

1
2
3
4
5
6
7
8
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
if (p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}

98. Validate Binary Search Tree

  • BST 条件
    1. left < root < right
    1. left and right subtree has to be valid BST

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

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public boolean isValidBST(TreeNode root) {
return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean helper(TreeNode node, long min, long max) {
if (node == null) {
return true;
}
if (node.val <= min || node.val >= max) {
return false;
}

// check left and right subtree
return helper(node.left, min, node.val) && helper(node.right, node.val, max);
}
}

Iterative (in-order traversal)

src: https://leetcode.com/problems/validate-binary-search-tree/discuss/32112/Learn-one-iterative-inorder-traversal-apply-it-to-multiple-tree-questions-(Java-Solution)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(pre != null && root.val <= pre.val) return false;
pre = root;
root = root.right;
}
return true;
}

Lowest Common Ancestor

235. Lowest Common Ancestor of a Binary Search Tree

  • proning is possible via BST property

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// already catch in last else{}
//if (p.val == root.val || q.val == root.val) {
// return root;
//}

if (p.val < root.val && q.val < root.val) {
return lowestCommonAncestor(root.left, p, q);
} else if (p.val > root.val && q.val > root.val) {
return lowestCommonAncestor(root.right, p, q);
} else {
// p.val < root.val && root.val < q.val) OR
// (q.val < root.val && root.val < p.val)
return root;
}
}
}

236. Lowest Common Ancestor of a Binary Tree

  • root is LCA when left and right is not null
  • pass LCA up to the real root as the return value

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == null || q == null) {
return null;
}

// parent
if (root == q || root == p) {
return root;
}

// from children
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);

if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
}

###Follow up:

  • 如果输入的node不在树里面怎么办
  • 如果两个node是相同的怎么办
  • 如果有两个Thread同时访问这棵树会不会有问题?可不可以有办法不用synchronized?

Depth/Height/Path

104. Maximum Depth of Binary Tree

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

recursive

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}

int left = maxDepth(root.left);
int right = maxDepth(root.right);

return Math.max(left, right) + 1;
}
}

iterative

Iterative approach has DFS and BFS.
DFS go through each of the leave node and update a global max along the way.
BFS maintains a count to record the max level when doing level order traversal, which the count is the max depth.

src: https://leetcode.com/problems/maximum-depth-of-binary-tree/discuss/34195/Two-Java-Iterative-solution-DFS-and-BFS

111. Minimum Depth of Binary Tree

  • careful to the difference from max depth above
  • BFS might works better than DFS since it is looking for the first leave node

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

DFS recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}

int left = minDepth(root.left);
int right = minDepth(root.right);

// important: difference here from max depth
if (left == 0 || right == 0) {
return left + right + 1;
}

return Math.min(left, right) + 1;
}
}

BFS iterative (preferred)

  • first leave node with both left == null and right == null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int minDepth(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
if (root == null) {
return 0;
}
int depth = 1;
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
root = queue.poll();
if (root.left == null && root.right == null) {
return depth;
}
if (root.left != null) {
queue.offer(root.left);
}
if (root.right != null) {
queue.offer(root.right);
}
}
depth++;
}
return depth;
}
}

110. Balanced Binary Tree [x]

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public boolean isBalanced(TreeNode root) {
int result = getDepthDiff(root);
return result == -1 ? false : true;
}

private static int getDepthDiff(TreeNode root) {
if (root == null) {
return 0;
}
int left = getDepthDiff(root.left);
int right = getDepthDiff(root.right);
if (left == -1 || right == -1) {
return -1;
}
if (Math.abs(left - right) > 1) {
return -1;
}
return Math.max(left, right) + 1;
}
}

112. Path Sum

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

  • path sum requires to check if current root is a leaf node (import)

recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) { // caution: need to check if it is a child node
if (root.val == sum) {
return true;
}
}

boolean left = hasPathSum(root.left, sum - root.val);
boolean right = hasPathSum(root.right, sum - root.val);

return left || right;
}
}

iterative: preorder traversal [x]

Similar solution as yours. Your solution has changed the internal tree node value, and in production code, this may be not permitted. Followed is my solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public boolean hasPathSum(TreeNode root, int sum) {
Stack<TreeNode> stack = new Stack<TreeNode>();
Stack<Integer> sums = new Stack<Integer>();

stack.push(root);
sums.push(sum);
while(!stack.isEmpty()&&(root!=null)){
int value = sums.pop();
TreeNode top = stack.pop();

if(top.left==null&&top.right==null&&top.val==value){
return true;
}
if(top.right!=null){
stack.push(top.right);
sums.push(value-top.val);
}
if(top.left!=null){
stack.push(top.left);
sums.push(value-top.val);
}

}
return false;
}

src: https://leetcode.com/problems/path-sum/discuss/36534/My-java-no-recursive-method

543. Diameter of Binary Tree

  • diameter is number of edges between two nodes
  • passing root is NOT required

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

recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private int max = 0;

public int diameterOfBinaryTree(TreeNode root) {
getPath(root);
return max;
}

private int getPath(TreeNode root) {
if (root == null) {
return 0;
}
int left = getPath(root.left);
int right = getPath(root.right);
max = Math.max(max, left + right);

return Math.max(left, right) + 1;
}
}

iterative (post-order traversal) [x]

https://leetcode.com/problems/diameter-of-binary-tree/discuss/124198/Iterative-Accepted-Java-Solution

124. Binary Tree Maximum Path Sum

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

  • definition of path is same as lc543 Diameter of Binary Tree
  • path sum return node value, hence, need to consider negative node value
1
2
3
4
5
// example for [key step]

1
/
-2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
private int max = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
getPath(root);
return max;
}

private int getPath(TreeNode root) {
if (root == null) {
return 0;
}
int left = Math.max(0, getPath(root.left)); // key step
int right = Math.max(0, getPath(root.right)); // key step
max = Math.max(max, left + right + root.val);
return root.val + Math.max(left, right);
}
}

Note: Iterative approach is also possible with post-order traversal but less straight forward in code aspect

Binary Search Tree (BST)

108. Convert Sorted Array to Binary Search Tree

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
return buildBST(nums, 0, nums.length-1);
}
public static TreeNode buildBST(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = buildBST(nums, left, mid-1);
root.right = buildBST(nums, mid+1, right);
return root;
}
}

recursive approach:
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/35218/Java-Iterative-Solution/33427

230. Kth Smallest Element in a BST

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

  • method1: inorder traversal of BST returns the k-th smallest with list.get(k-1)
  • method2: count total of node and use binary search to locate kth element

Recurisve

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int kthSmallest(TreeNode root, int k) {
List<Integer> sorted = new ArrayList<Integer>();
inorderTraversal(root, sorted);
return sorted.get(k-1); // kth smallest -> index: k-1
}
public static void inorderTraversal(TreeNode node, List<Integer> list) {
if (node == null) {
return;
}

inorderTraversal(node.left, list);
list.add(node.val);
inorderTraversal(node.right, list);
}
}

Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int kthSmallest(TreeNode root, int k) {
TreeNode node = root;
Deque<TreeNode> stack = new ArrayDeque<>();
int count = 0;

while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
count++;
if (count == k) return node.val;
node = node.right;
}
return -1;
}
}

173. Binary Search Tree Iterator

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

  • inorder traversal for BST returns a sorted list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

public class BSTIterator {

private static Deque<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new ArrayDeque<>();
pushLeftSubtree(root);
}

/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}

/** @return the next smallest number */
public int next() {
TreeNode node = stack.pop();
int nextVal = node.val;
node = node.right;
pushLeftSubtree(node);

return nextVal;
}

private void pushLeftSubtree(TreeNode root) {
while (root != null) {
stack.push(root);
root = root.left;
}
}
}

/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/

Tree Traversal

Preorder

https://leetcode.com/problems/binary-tree-preorder-traversal/description/

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ArrayList<Integer> preorderTraversal(TreeNode root) {
// write your code here
List<Integer> list = new ArrayList<Integer>();
getValue(root, list);
return list;
}
private void getValue(TreeNode root, ArrayList<Integer> list) {
// base case
if (root == null) {
return;
}

// preorder
list.add(root.val);
getValue(root.left, list);
getValue(root.right, list);
}

Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Preorder in ArrayList which contains node values.
*/
public ArrayList<Integer> preorderTraversal(TreeNode root) {
// write your code here
Stack<TreeNode> stack = new Stack<TreeNode>();
ArrayList<Integer> preorder = new ArrayList<Integer>();
if (root == null) {
return preorder;
}
stack.push(root);
while (!stack.empty()) {
TreeNode curr = stack.pop();
preorder.add(curr.val);

if (curr.right != null) { // import: stack, push right first
stack.push(curr.right);
}
if (curr.left != null) {
stack.push(curr.left);
}
}
return preorder;
}
}

Iterative w/ Guide Class

  • use Guide class helps to improve code reusabliity and flexibility
  • ops should be reversely pushed into stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {

List<Integer> result = new ArrayList<>();
Deque<Guide> stack = new ArrayDeque<>();
stack.push(new Guide(0, root));

while (!stack.isEmpty()) {
Guide guide = stack.pop();
if (guide.node == null) { // defensive coding
continue;
} else if (guide.op == 1) {
result.add(guide.node.val);
} else {
// ops:
// print root.val
// visit root.left
// visit root.right

stack.push(new Guide(0, guide.node.right));
stack.push(new Guide(0, guide.node.left));
stack.push(new Guide(1, guide.node));
}
}

return result;
}

private class Guide {
int op; // 0: visit 1: print
TreeNode node;

public Guide(int op, TreeNode node) {
this.node = node;
this.op = op;
}
}
}

Inorder

https://leetcode.com/problems/binary-tree-inorder-traversal/description/

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ArrayList<Integer> preorderTraversal(TreeNode root) {
// write your code here
List<Integer> list = new ArrayList<Integer>();
getValue(root, list);
return list;
}
private void getValue(TreeNode root, ArrayList<Integer> list) {
// base case
if (root == null) {
return;
}

// inorder
getValue(root.left, list);
list.add(root.val);
getValue(root.right, list);
}

Iterative v1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Inorder in ArrayList which contains node values.
*/
public List<Integer> inorderTraversal(TreeNode root) {
// write your code here
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> inorder = new ArrayList<Integer>();

TreeNode curr = root;
while (curr != null || !stack.empty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
inorder.add(curr.val);
curr = curr.right;
}
return inorder;
}
}

Iterative w/ Guide Class

  • use Guide class helps to improve code reusabliity and flexibility
  • ops should be reversely pushed into stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {

List<Integer> result = new ArrayList<>();
Deque<Guide> stack = new ArrayDeque<>();
stack.push(new Guide(0, root));

while (!stack.isEmpty()) {
Guide guide = stack.pop();
if (guide.node == null) { // defensive coding
continue;
} else if (guide.op == 1) {
result.add(guide.node.val);
} else {
// ops:
// visit root.left
// print root.val
// visit root.right

stack.push(new Guide(0, guide.node.right));
stack.push(new Guide(1, guide.node));
stack.push(new Guide(0, guide.node.left));
}
}

return result;
}

private class Guide {
int op; // 0: visit 1: print
TreeNode node;

public Guide(int op, TreeNode node) {
this.node = node;
this.op = op;
}
}
}

Postorder

https://leetcode.com/problems/binary-tree-postorder-traversal/description/

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ArrayList<Integer> preorderTraversal(TreeNode root) {
// write your code here
List<Integer> list = new ArrayList<Integer>();
getValue(root, list);
return list;
}
private void getValue(TreeNode root, ArrayList<Integer> list) {
// base case
if (root == null) {
return;
}

// inorder
getValue(root.left, list);
getValue(root.right, list);
list.add(root.val);
}

Iterative v1

  • indeed the reverse order of level-order traversal
  • since does NOT required output to be level ordred (just single list), use stack instead
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
if (root == null) return ans;

stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
ans.addFirst(cur.val);
if (cur.left != null) {
stack.push(cur.left);
}
if (cur.right != null) {
stack.push(cur.right);
}
}
return ans;
}
}

Iterative w/ Guide Class

  • use Guide class helps to improve code reusabliity and flexibility
  • ops should be reversely pushed into stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {

List<Integer> result = new ArrayList<>();
Deque<Guide> stack = new ArrayDeque<>();
stack.push(new Guide(0, root));

while (!stack.isEmpty()) {
Guide guide = stack.pop();
if (guide.node == null) { // defensive coding
continue;
} else if (guide.op == 1) {
result.add(guide.node.val);
} else {
// ops:
// visit root.left
// visit root.right
// print root.val

stack.push(new Guide(1, guide.node));
stack.push(new Guide(0, guide.node.right));
stack.push(new Guide(0, guide.node.left));
}
}

return result;
}

private class Guide {
int op; // 0: visit 1: print
TreeNode node;

public Guide(int op, TreeNode node) {
this.node = node;
this.op = op;
}
}
}

Levelorder

102. Binary Tree Level Order Traversal

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public List<List<Integer>> levelOrder(TreeNode root) {
// write your code here
Deque<TreeNode> queue = new ArrayDeque<TreeNode>();
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) {
return result;
}
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> currLevel = new ArrayList<Integer>();
int size = queue.size();

for (int i = 0; i < size; i++) {
TreeNode curr = queue.remove();
currLevel.add(curr.val);

if (curr.left != null) {
queue.add(curr.left);
}
if (curr.right != null) {
queue.add(curr.right);
}
}
result.add(currLevel);
}
return result;
}
}

DFS

DFS recursive appraoch https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/33445/Java-Solution-using-DFS

103. Binary Tree Zigzag Level Order Traversal

  • same to level order, reverse list order on ODD level

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Solution {
/*
* @param root: A Tree
* @return: A list of lists of integer include the zigzag level order traversal of its nodes' values.
*/
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
// write your code here
Deque<TreeNode> queue = new ArrayDeque<>();
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
queue.add(root);

int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> levelList = new ArrayList<>();

for (int i = 0; i < size; i++) {
TreeNode node = queue.remove();
levelList.add(node.val);

if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
if (level % 2 == 1) {
Collections.reverse(levelList);
}

result.add(levelList);
level++;
}
return result;
}
}

Tree Reconstruction

297. Serialize and Deserialize Binary Tree

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

DFS prefered (preorder traversal)

  • preferred cuz less code complexity
  • any one kind of traversal should work
  • buildString() buildTree() method
  • buildString with pre-order traversal
  • using StringBuilder for buildString()
  • using Queue for buildTree()
  • why this work? since both buildString() & buildTree() uses the same pre-order traversal, which garntee the results are the same
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// ref: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/discuss/74253/Easy-to-understand-Java-Solution

public class Codec {
private static final String spliter = ",";
private static final String NN = "X";

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
buildString(root, sb);
return sb.toString();
}

private void buildString(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append(NN).append(spliter);
} else {
sb.append(node.val).append(spliter);
buildString(node.left, sb);
buildString(node.right,sb);
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Deque<String> nodes = new ArrayDeque<>();
nodes.addAll(Arrays.asList(data.split(spliter)));
return buildTree(nodes);
}

private TreeNode buildTree(Deque<String> nodes) {
String val = nodes.remove();
if (val.equals(NN)) return null;

TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = buildTree(nodes);
node.right = buildTree(nodes);
return node;
}
}

BFS w/ queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class Code {

private static final String spliter = ",";
private static final String NN = "X";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
Deque<TreeNode> queue = new ArrayDeque<>();
if (root == null) {
return "";
}
queue.add(root);
sb.append(root.val).append(spliter);

while (!queue.isEmpty()) {
TreeNode curr = queue.remove();
if (curr.left == null) {
sb.append(NN).append(spliter);
} else {
queue.add(curr.left);
sb.append(curr.left.val).append(spliter);
}
if (curr.right == null) {
sb.append(NN).append(spliter);
} else {
queue.add(curr.right);
sb.append(curr.right.val).append(spliter);
}
}
return sb.toString(); // output complete binary tree
}

// BFS: Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
TreeNode root = null;
if (data == null || data.length() == 0) {
return root;
}
String[] nodes = data.split(spliter);
Deque<TreeNode> queue = new ArrayDeque<>();
root = new TreeNode(Integer.parseInt(nodes[0]));
queue.add(root);

for (int i = 1; i < nodes.length && !queue.isEmpty(); i++) {
TreeNode curr = queue.poll();

if (!nodes[i].equals(NN)) {
curr.left = new TreeNode(Integer.parseInt(nodes[i]));
queue.offer(curr.left);
}
i++;
if (!nodes[i].equals(NN)) {
curr.right = new TreeNode(Integer.parseInt(nodes[i]));
queue.offer(curr.right);
}
}
return root;
}
}

449. Serialize and Deserialize BST

  • as compact as possible (wo/ X or #)
  • using two traverals (eg. preorder + inorder) to reconstruct
  • solution 297 should also work for this porblem but less effiicent in space

One traversal (preorder + BST property)

1
preorder:   | root | left subtree | right subtree |

Since it is a BST, first value larger than root belongs to right subtree. we can use this property to reconstruct BST with just single traversal

Important takehome:

  • BST can be reconstructed with ONE preorder traversal + BST property
  • Binary Tree required at least TWO traversals we cannot take advantage of BST property

105. Construct Binary Tree from Preorder and Inorder Traversal

1
2
preorder:	| root | left subtree | right subtree |
inorder: | left subtree | root | right subtree |

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

Observations:

    1. preorder: first element of preorder is always the root of current subtree
    1. inorder: once root found, in inorder array, left of root is left subtree, and right of root is right subtree.
    1. preorder: Once we know the number of elements in left subtree and right subtree, we could find the corresponding roots for left subtree and right subtree from preorder array.
    1. recursively repeat step 1-3.

Implementations:

  • the hardest part of this question is to determine what indices are needed for the helper function
  • inStart and inEnd indicates the range of current subtree in inorder array
  • pStart tells the location of the root for current subtree (preorder[pStart])

ref: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34538/My-Accepted-Java-Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) {
return null;
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return buildHelper(preorder, inorder, map, 0, 0, preorder.length-1);
}

private TreeNode buildHelper(int[] preorder, int[] inorder, Map<Integer, Integer> map, int pStart, int inStart, int inEnd) {
if (inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(preorder[pStart]);

int inorderRootIdx = map.get(root.val);
root.left = buildHelper(preorder, inorder, map, pStart + 1, inStart, inorderRootIdx-1);
root.right = buildHelper(preorder, inorder, map, pStart + inorderRootIdx - inStart + 1, inorderRootIdx + 1, inEnd);
return root;
}
}

106. Construct Binary Tree from Inorder and Postorder Traversal

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

  • note: postStart here is acutally the last element in ordering of the subtree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
TreeNode root = build(inorder, 0, inorder.length - 1, postorder, postorder.length - 1);
return root;
}

public TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart) {
if (inStart > inEnd || postStart < 0) return null; // postStart < 0 defensive coding

TreeNode root = new TreeNode(postorder[postStart]);
int index = inStart;
for (index = inStart; index < inEnd; index++) {
if (inorder[index] == postorder[postStart]) {
break;
}
}
// int rightCount = inEnd - index;

root.left = build(inorder, inStart, index-1, postorder, postStart-(inEnd - index) -1);
root.right = build(inorder, index+1, inEnd, postorder, postStart-1);
return root;
}
}

Logs

  • 06/02/2018: first draft finished
  • 07/11/2018: revisited all questions & checked LC discussion
  • 11/08/2018: add DFS approach for serialize & deserialize BST
  • 05/11/2019: add Difference between #297 and #449 (serialize and deserialize BST & BT)
  • 09/08/2019: updated binary tree & BST reconstruction