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,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Solution 1: do BFS, using two queues. One store the trees, and the other store the levels.

Java语言: BinaryTreeLevelOrderTraversal

01 public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {

02   ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();

03   ArrayList<TreeNode> trees=new ArrayList<TreeNode>();

04   ArrayList<Integer> depth=new ArrayList<Integer>();

05   ArrayList<Integer> firstLevel=new ArrayList<Integer>();

06 

07   if(root==null)

08     return results;          

09   trees.add(root);

10   depth.add(1);

11   firstLevel.add(root.val);

12   results.add(firstLevel);

13   while(!trees.isEmpty())

14   {

15     TreeNode top=trees.remove(0);

16     int curr_val=depth.remove(0);

17     if(top.left!=null)

18     {

19       trees.add(top.left);

20       depth.add(curr_val+1);

21     }

22     if(top.right!=null)

23     {

24       trees.add(top.right);

25       depth.add(curr_val+1);

26     }

27     int size=depth.size();

28     if(size>0 && depth.get(0)==depth.get(size-1) && curr_val==depth.get(0)-1)

29     {

30       ArrayList<Integer> curr_level=new ArrayList<Integer>();

31       for(int i=0;i<trees.size();i++)

32       {

33         curr_level.add(trees.get(i).val);

34       }

35       results.add(curr_level);

36     }

37   }

38   return results;

39 }

Solution 2: still using BFS and two queues. But both queue store the tree nodes, the current level and the next level. One the current level is empty but next level is not, output the result.

Java语言: BinaryTreeLevelOrder

01 public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {

02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>> ();

03     if(root==null)

04         return results;

05     LinkedList<TreeNode> thisLevel = new LinkedList<TreeNode>();

06     LinkedList<TreeNode> nextLevel = new LinkedList<TreeNode>();

07     thisLevel.add(root);

08     ArrayList<Integer> firstLine=new ArrayList<Integer>();

09     firstLine.add(root.val);

10     results.add(firstLine);

11     while(thisLevel.size()!=0)

12     {

13         TreeNode node = thisLevel.peek();

14         if(node.left!=null)

15         {

16             nextLevel.add(node.left);

17         }

18         if(node.right!=null)

19         {

20             nextLevel.add(node.right);

21         }

22         thisLevel.remove();

23         if(thisLevel.size()==0 && nextLevel.size()!=0)

24         {

25             ArrayList<Integer> level=new ArrayList<Integer>();

26             for(TreeNode n: nextLevel)

27             {

28                 level.add(n.val);

29             }

30             results.add(level);

31             thisLevel = nextLevel;

32             nextLevel = new LinkedList<TreeNode>();

33         }

34     }      

35     return results;

36 }

Solution 3: as BFS maintains two queues and is complex. A DFS method looks easier and concise. We just do a DFS, always remember the level of the current node, and assign the node to the correct level in the result list, then we are done!

Java语言: BinaryTreeLevelOrderDFS

01 public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
03     if(root==null)
04         return results;
05     //Start DFS from the root, level=0    
06     levelOrderDFS(results,root,0);
07     return results;
08 }
09 public void levelOrderDFS(ArrayList<ArrayList<Integer>> results, TreeNode node, int level)
10 {
11     //reach a new level, and created this level, add the node
12     if(results.size()-1<level)
13     {
14         ArrayList<Integer> newLevel=new ArrayList<Integer>();
15         newLevel.add(node.val);
16         results.add(newLevel);
17     }
18     //append the node to the existing level it correspond to
19     else
20     {
21         ArrayList<Integer> existLevel=results.get(level);
22         existLevel.add(node.val);
23         results.set(level,existLevel);
24     }
25     //DFS recursion on left and right respectively
26     if(node.left!=null)
27     {
28         levelOrderDFS(results,node.left,level+1);
29     }
30     if(node.right!=null)
31     {
32         levelOrderDFS(results,node.right,level+1);
33     }
34 }

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Hint: we first provide an obvious method, a recursion version. The idea behind it is to use the pre-order traversal of a binary tree.

Java语言: FlattenBinaryTree

01 public void flatten(TreeNode root) {
02     if(root==null)
03         return;
04     if(root.left!=null)
05     {
06         TreeNode rChild=root.right;
07         root.right=root.left;
08         root.left=null;
09         TreeNode rightMost=root.right;
10         while(rightMost.right!=null)
11         {
12             rightMost=rightMost.right;
13         }
14         rightMost.right=rChild;          
15     }
16   
17     flatten(root.right);      
18 }

Consider how the pre-order traversal is accomplished inside? We may use a stack to to so.

01 import java.util.*;
02 public class Solution {
03     public void flatten(TreeNode root) {
04         if(root==null)
05             return;
06               
07         TreeNode curr=null;
08         Stack<TreeNode> trees=new Stack<TreeNode>();
09         trees.add(root);
10         while(!trees.empty())
11         {
12             TreeNode parent=trees.pop();
13               
14             if(parent.right!=null)
15             {
16                 trees.push(parent.right);
17             }
18           
19             if(parent.left!=null)
20             {
21                 trees.push(parent.left);
22             }
23             parent.left=null;
24             parent.right=null;
25             if(root==parent)
26             {                                              
27                 curr=parent;
28             }
29             else
30             {              
31                 curr.right=parent;
32                 curr=curr.right;
33             }
34         }
35       
36     }
37 }

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

This is a follow up question of Path Sum. Note that the values along the path may contain negative values.

Java语言: PathSumII

01 public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
02   ArrayList<ArrayList<Integer>>results=new ArrayList<ArrayList<Integer>>();
03   ArrayList<Integer> temp=new ArrayList<Integer>();
04   findPath(results,temp,root,sum);
05   return results;
06 
07 }
08 public void findPath(ArrayList<ArrayList<Integer>>results,ArrayList<Integer>temp,TreeNode root, int sum)
09 {
10   if(root==null)
11     return;
12   if(root.val==sum && root.left==null && root.right==null)
13   {
14     temp.add(root.val);
15     ArrayList<Integer>out=new ArrayList<Integer>();
16     for(int i=0;i<temp.size();i++)
17     {
18       out.add(temp.get(i));
19     }
20     results.add(out);
21   }
22   else
23   {
24     temp.add(root.val);
25     findPath(results,temp,root.left,sum-root.val);
26     findPath(results,temp,root.right,sum-root.val);
27   }
28   int size=temp.size();
29   if(size>0)
30   {
31     temp.remove(size-1);
32   }
33 
34 }

Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Java语言: PathSum

01 public boolean hasPathSum(TreeNode root, int sum) {
02   if(root==null)
03   {
04     return false;
05   }
06   if(root.left==null && root.right==null)
07   {
08     if(root.val==sum)
09       return true;
10     else
11       return false;
12   }
13   return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
14 }

Depth of Binary Tree

Given a binary tree, find its depth (maximum height).

There are several methods to solve this problem.
The recursion way is straightforward. How about iterative ways?
We first use an in-order traversal method.

01 public int maxHeight(TreeNode root) {

02    if(root==null)
03        return 0;
04    Stack<TreeNode>trees=new Stack<TreeNode>();
05    Stack<Integer>depth=new Stack<Integer>();
06    trees.push(root);
07    int curr_depth=1;
08    depth.push(curr_depth);
09    int maxDepth=1;
10    TreeNode leftNode=root.left;
11    while(leftNode!=null)
12    {
13      
14        trees.push(leftNode);
15        leftNode=leftNode.left;
16        curr_depth++;
17        depth.push(curr_depth);
18      
19    }
20    while(!trees.isEmpty())
21    {
22        TreeNode top=trees.pop();
23        curr_depth=depth.pop();
24        if(curr_depth>maxDepth)
25        {
26            maxDepth=curr_depth;
27        }
28        TreeNode rightNode=top.right;
29        curr_depth++;
30        if(rightNode!=null)
31        {
32            trees.push(rightNode);                              
33            depth.push(curr_depth);
34            TreeNode leftmost=rightNode.left;
35            while(leftmost!=null)
36            {
37                trees.push(leftmost);
38                leftmost=leftmost.left;
39                curr_depth++;
40                depth.push(curr_depth);
41            }
42        }
43    }
44    return maxDepth;
45 }

We can also use a recursion way to solve it.

Java语言: 高亮代码由发芽网提供

01 public class Solution {
02     public int maxHeight(TreeNode root) {
03         if(root==null)
04             return 0;
05         else
06         {
07             return findMax(maxHeight(root.left),maxHeight(root.right))+1;
08         }
09       
10     }
11   
12     public int findMax(int a, int b)
13     {
14         return a>b?a:b;
15     }
16 }

[Repost from LeetCode] 转一些我blog上一些常见的二叉树面试问题和总结 (更新)

二叉树是面试里常见的问题种类，大家在面试前必须熟悉这一类的问题。以下是我收集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌握好。我会在这里更新和添加常见到的二叉树问题。

Determine if a Binary Tree is a Binary Search Tree
这题很常见，microsoft,amazon, google的面试都有人被问过。这题也是二叉树的好题
，必须得对BST的定义搞清楚。有一个常见的陷阱，就是把current node的value和left
node, right node比较；这是不正确的解法。也有一个很容易想到的brute force解法
，但是每个node会被遍历很多次。正确的优解是 （O(N)解，N=number of nodes)有两
种，面试者必须对这题熟悉。

Binary Search Tree In-Order Traversal Iterative Solution
这题应该是 google 电面经常问的问题吧。我那时候就是google电面没答好这问题，所
以就fail了，超级后悔啊。强烈推荐的问题。In-Order traversal能很轻松地用递归来
实现（就是常见的DFS），但非递归怎么解呢？总结就是，DFS的特性是用stack。常见
的DFS题都是用递归，哪来的stack啊？其实递归就是把function push 上memory stack
，一旦function结束了就从memory stack pop出来。所以DFS可以转换成非递归的解法
，就是利用stack的辅助。基本上有两种解法，比较容易的是在每个节点上加一个visited field。那如果是第二次遍历这个节点那就打印出来。更好的解法是不用visited field的。如果觉得这题对你来说太难的话，先尝试 pre-order traversal吧。另一方面如果这题对你不够挑战性，那请你尝试 post-order traversal，比起 in-order 难多了。

Printing a Binary Tree in Level Order
好像 facebook 满喜欢问这问题。这题是很基础的用breadth-first search(BFS)，面
试者必须熟悉。这题也能用DFS来解，而且时间复杂度也是O(N)。BFS的特性是使用
queue，而DFS的特性是用stack。

Printing a Binary Tree in Zig-Zag Level Order
这题是上题的一个变种，就是从上到下，然后反复从左到右，右到左的打印树。这次我
们不用queue了。用另一种data structure来储存，就可以很容易地办到。

Populating Next Right Pointers in Each Node
这题就是把所有node的next right指针指向右边邻居（right sibling）（一开始全被初始化为null）。如果没有邻居，应该指向null。你可以假设二叉树是满的。这题的诀窍在于利用DFS的思路，再加上善用之前节点已经连接好的巧妙之处，就能轻松解决。
很不错的二叉树问题。

Finding the Maximum Height of a Binary Tree
这题就是寻找二叉树的最深度，利用DFS可以轻松解决。挑战的是：如何写非递归的版本。有两种解法，一是用BFS，解法比较直接。另一种解法是转换成非递归BFS，方法请参考In-Order Traversal Iterative Solution.

Serialization/Deserialization of Binary Tree
"Serialization"的定义为把二叉树储存于文档里，而"Deserialization"的定义为把二叉树从文档里读取，恢复之前的状态。答案就是利用pre-order可以办得到，关键在于你必须掌握pre-order,post-order,和in-order之间的特性。还有需要理解为什么二叉树要储存NULL node，而重建BST就不需要（看下题）。

Rebuild Binary Search Tree from Pre-order Traversal
输入是从BST用pre-order traversal打印出来的data，请问怎么重建BST? 总结就是：当我们遇到一个即将被植入的节点，第一个能被植入的空间而且也符合BST的要求，就是正确的地方。每次植入的时候都检测是不是BST就应用了之前“Determine if a Binary Tree is a Binary Search Tree”一模一样的思路。检测只需要O(1)，那么重建树就只需要O(N).

Print Edge Nodes (Boundary) of a Binary Tree
这题好像是微软面试题，满好玩的。问题是要把树的周围 counter-clockwise 打印出来。先打印root，然后从上到下打印最左边的节点，然后从左到右的顺序打印叶子节点，然后从下到上打印最右边的节点。这题的精粹就在于使用depth-first traversal，一个递归就能搞定。先把树分为两个树（root的左孩子和右孩子）处理。先处理左树，再处理右树。如果卡在怎么从下到上打印最右边节点，可以想想post-order traversal。

Binary Tree Post-Order Traversal Iterative Solution
这题比起 In-Order Traversal 难多了。是很罕见的面试题，好像只有 amazon 问过这道题。用 visited flags 好做很多，但是不用 visited flags 还是有可能解出来的。思路就是利用一个变量储存之前访问的节点。然后在每次循环的时候比较之前节点和 stack 上的节点，这样就可以知道我们在往上还是往下走。如果往上走的话，就能得知是从左节点还是右节点上来的，这有大大的帮助。另外一个方法是使用两个 stack，解法很简洁，很巧妙，但是空间复杂度没有一个 stack 的解法少。