Binary Tree Maximum PathSum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Solution: this answer use a post-order traversal. Note that in Java we cannot pass int variables by reference, therefore we need to pass an ArrayList object to keep and modify the current max value.

Java语言: BinaryTreeMaxPathSum

01 public int maxPathSum(TreeNode root) {
02     ArrayList<Integer> temp = new ArrayList<Integer>(1);
03     temp.add(Integer.MIN_VALUE);
04     maxSubPath(root, temp);
05     return temp.get(0);
06 }
07 
08 public int maxSubPath(TreeNode root, ArrayList<Integer> temp) {
09     if (root == null)  return 0;
10     int leftMax = Math.max(0, maxSubPath(root.left, temp));
11     int rightMax = Math.max(0, maxSubPath(root.right, temp));
12     int curr_max=temp.get(0);
13     int new_max= root.val+leftMax+rightMax;
14       //update the max path sum
15     if(new_max>curr_max)
16         temp.set(0, new_max);
17     //calculate the max sub path, 
18     //either on left branch or right branch
19     return Math.max(root.val+leftMax, root.val+rightMax);
20 }

Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

If you are not so sure about the definition of lowest common ancestor (LCA), please refer to my previous post:Lowest Common Ancestor of a Binary Search Tree (BST) or the definition of LCA here. Using the tree above as an example, the LCA of nodes 5 and 1 is 3. Please note that LCA for nodes 5 and 4 is 5.

Solution 1:
We can use a bottom-up approach. Find the first occurrence of two nodes from left sub-tree and right sub-tree respectively. Check whether these two occurrence lie on two different branches. If it is the case, return the root. Other wise, the first occurrence of the nodes must be either on the left branch or on the right branch. At this time, we already found the the ancestor node in one of the sub-tree, then we just return it.

Java语言: LCA

01 public TreeNode LCA(TreeNode root,TreeNode p, TreeNode q)

02 {

03     //base cases

04     if(root==null)

05         return null;

06     if(root==p || root==q)

07         return root;

08     TreeNode left=LCA(root.left,p,q);

09     TreeNode right=LCA(root.right,p,q);

10     //p and q are on the different branches, return root

11     if(left!=null && right!=null)

12         return root;

13     //p and q are on the same branch

14     else if(left!=null)

15         return left;

16     else

17         return right;

18 }

Solution 2:

As some of us may imagine, if we have a parent node of each node, then the question becomes very easy, we just check whether two nodes can be the same when they are climbing up from their parents to the root. If there is no such parent pointer, we can also construct the parent pointer ourselves. How? We can use hash tables! We do a pre-order (DFS) traversal, and in this process we keep inserting child->parent pairs into the hash table. Then we are able to climb up. In addition, we use another hash table to keep the depth of each node, the purpose of this is that this can make our process easy. We always climb up from the node at the lower level, until they reach the same level. If then they are still not equal, we just make them climbing up together, until they meet at somewhere.

Java语言: LCA2

01 public TreeNode LCA2(TreeNode root,TreeNode p, TreeNode q)
02 {
03     //handle special cases first
04     if(root==null)
05         return null;
06     if(root==p||root==q)
07         return root;
08     Hashtable<TreeNode,TreeNode> parents=new Hashtable<TreeNode,TreeNode>();
09     Hashtable<TreeNode, Integer> levels=new Hashtable<TreeNode,Integer>();      
10     //parents.put(root, null);
11     levels.put(root, 1);
12   
13     //DFS(preorder) the tree, after that the parents and levels are assigned
14     DFS(root,parents,levels);
15     int level_p=levels.get(p);
16     int level_q=levels.get(q);
17     while(level_p<level_q)
18     {
19         q=parents.get(q);
20         level_q--;
21     }
22     while(level_p>level_q)
23     {
24         p=parents.get(p);
25         level_p--;
26     }
27     while(p!=q)
28     {
29         p=parents.get(p);
30         q=parents.get(q);
31     }
32     return p;
33 }
34 
35 public void DFS (TreeNode node, Hashtable<TreeNode,TreeNode> parents,Hashtable<TreeNode, Integer> levels)
36 {
37     int level=levels.get(node);
38     if(node.left!=null)
39     {
40         parents.put(node.left, node);
41         levels.put(node.left, level+1);
42         DFS(node.left,parents,levels);
43     }
44     if(node.right!=null)
45     {
46         parents.put(node.right,node);
47         levels.put(node.right, level+1);
48         DFS(node.right,parents,levels);
49     }
50 }

The Width of a Binary Tree

The width of a binary tree is defined as the maximum number of nodes of the same level. Assume a binary tree is like

        1

     /    \

   2       3

 /   \    /  \

4    5   6    7

Then the width of the tree is 4.

Write an algorithm to get the width of a binary tree.

Hint: a Breadth-First Search method may come to your mind immediately. However, can you use Depth First Search?

Solution: do a pre-order traversal. Using an array to keep track of the number of nodes in each level. When you visit a node, increment the number of the current level by 1. Since you won't visit it again, each tree node is counted only once.

Java语言: WidthOfBinaryTree

01 public int maxWidth(TreeNode root)
02 {
03     if(root==null)
04         return 0;
05     //define an array to record the number of nodes in each level
06     //assume the max number of levels is 1000
07     int []levels=new int[1000];
08     int max=0;
09     maxWidthHelper(levels,0,root);
10     //iterate through the level array, find max
11     for(int i=0;i<1000;i++)
12     {
13         if(levels[i]>max)
14         {
15             max=levels[i];
16         }
17     }
18     return max;
19 }
20 
21 public void maxWidthHelper(int [] levels, int depth, TreeNode root)
22 {
23     if(root==null)    return;
24     //visit this node, increment the number of nodes in the current level
25     levels[depth]++;
26     //DFS on children of the next level
27     maxWidthHelper(levels, depth+1, root.left);      
28     maxWidthHelper(levels, depth+1, root.right);      
29 }

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 }