[LeetCode] Tree题目

MengMa

Balanced Binary Tree


思路：
递归。helper()既表示高度又表示真假。

复杂度：
空间 O（logn）  时间 O（n）(全部节点)

错误： 忘记 if(left <0 || right < 0 ) return -1; //Forgot this..

1. public class Solution {
   
2.     public boolean isBalanced(TreeNode root) {
   
3.         return helper(root) >= 0;
   
4.     }
   
5.     public int helper(TreeNode root)
   
6.     {
   
7.         if(root == null)
   
8.             return 0;
   
9.         if(root.left == null && root.right == null) return 1;
   
10.         int left = helper(root.left);
    
11.         int right = helper(root.right);
    
12.         if(left <0 || right < 0 ) return -1; //Forgot this..
    
13.         if(Math.abs(left - right) > 1) return -1;
    
14.         else
    
15.             return Math.max(left, right) + 1;
    
16.     }
    
17. }

复制代码

迭代做法:没有想到如何不需要改变树节点结构就能迭代遍历的。。
http://www.careercup.com/question?id=6463905379385344

MengMa

Binary tree level order II

思路：
和binary tree level order完全一样。。最后加一句 Collections.reverse(res)
时间和空间都是 O（n）

1. public class Solution {
   
2.     public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
   
3.         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
   
4.         if(root == null) return res;
   
5.         LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
   
6.         queue.add(root);
   
7.         int curNum = 1;
   
8.         int nextNum = 0;
   
9.         ArrayList<Integer> tmp = new ArrayList<Integer>();
   
10.         while(!queue.isEmpty())
    
11.         {
    
12.             TreeNode cur = queue.poll();
    
13.             curNum --;
    
14.             tmp.add(cur.val); //when it gets poped, means visited, means need to add value
    
15.             if(cur.left!= null) //this is cur, not root
    
16.             {
    
17.                 queue.add(cur.left);
    
18.                 nextNum++;
    
19.             }
    
20.             if(cur.right != null)
    
21.             {
    
22.                 queue.add(cur.right);
    
23.                 nextNum++;
    
24.             }
    
25.             if(curNum == 0)
    
26.             {
    
27.                 curNum = nextNum;
    
28.                 nextNum = 0;
    
29.                 res.add(tmp);
    
30.                 tmp = new ArrayList<Integer>();
    
31.             }
    
32.         }
    
33.         Collections.reverse(res);
    
34.         return res;
    
35.     }
    
36. }

复制代码

MengMa

Binary Tree Level Order Traversal
思路：用一个queue来按层装节点。

用两个变量对当前层curNum和下一层nextNum计数。用一个ArrayList<Integer> tmp来记录当前层的所有values
每访问一个当前层节点，同时，判断有无左右子，按顺序加好，为nextNum++。 curNum--. 直到curNum变0， 把当前的tmp加入到结果res中。
curNum = 0时要为他赋新值，即原nextNum值。预示进入下一层迭代。

时间是O（n）, 空间是O（每层最多节点），也是O（n）

1. public class Solution {
   
2.     public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
   
3.         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
   
4.         if(root == null) return res;
   
5.         LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
   
6.         queue.add(root);
   
7.         int curNum = 1;
   
8.         int nextNum = 0;
   
9.         ArrayList<Integer> tmp = new ArrayList<Integer>();
   
10.         while(!queue.isEmpty())
    
11.         {
    
12.             TreeNode cur = queue.poll();
    
13.             curNum --;
    
14.             tmp.add(cur.val); //when it gets poped, means visited, means need to add value
    
15.             if(cur.left!= null) //this is cur, not root
    
16.             {
    
17.                 queue.add(cur.left);
    
18.                 nextNum++;
    
19.             }
    
20.             if(cur.right != null)
    
21.             {
    
22.                 queue.add(cur.right);
    
23.                 nextNum++;
    
24.             }
    
25.             if(curNum == 0)
    
26.             {
    
27.                 curNum = nextNum;
    
28.                 nextNum = 0;
    
29.                 res.add(tmp);
    
30.                 tmp = new ArrayList<Integer>();
    
31.             }
    
32.         }
    
33.         return res;
    
34.     }
    
35. }

复制代码

MengMa

Binary Tree Inorder Traversal

思路1：迭代的
对于当前访问节点root, 如果root不为null, 将该节点push， 同时root = root.left, 这时候如果有左子就持续进栈，直到走到最左侧。如果root == null，可以pop并访问了。需要把root = root.right。这样能让有孩子的右孩子进栈。如果没有孩儿，root变空了，那就继续pop
注意：stack.pop()可以构成2连击。即pop完当前节点后，下次pop要么是这个节点的右子树的根，要么就是这个节点的parent.


复杂度：
时间是O （n）, 空间上 O（logn）

1. public ArrayList<Integer> inorderTraversal(TreeNode root) {
   
2.        ArrayList<Integer> res = new ArrayList<Integer>();
   
3.         if(root == null) return res;
   
4.         LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
   
5.         while(root != null || !stack.isEmpty())
   
6.         {
   
7.             if(root != null)
   
8.             {
   
9.                 stack.push(root);
   
10.                 root = root.left;
    
11.             }
    
12.             else
    
13.             {
    
14.                 root = stack.pop();
    
15.                 res.add(root.val);
    
16.                 root = root.right;
    
17.             }
    
18.         }
    
19.         return res;
    
20.     }

复制代码

思路2：递归的感觉应该人人都会，所以也没有考得必要吧。
空间复杂度O（logn）时间复杂度O（n）

1.     public ArrayList<Integer> inorderTraversal(TreeNode root) {
   
2.         ArrayList<Integer> res = new ArrayList<Integer>();
   
3.         helper(root, res);
   
4.         return res;
   
5.     }
   
6.     private void helper(TreeNode root, ArrayList<Integer> res)
   
7.     {
   
8.         if(root == null) return;
   
9.         helper(root.left, res);
   
10.         res.add(root.val);
    
11.         helper(root.right, res);
    
12.     }

复制代码

MengMa

Binary Tree Maximum Path Sum


思路：
Big picture是用递归来解决这个问题。需要一个global变量来存储并update当前最大的path sum。
递归函数每次返回的计算值会被 其他节点（父节点） 用于计算自身的path sum, 所以递归函数返回的只能是一侧的path sum。
这里一侧的意思是“根val + 根左子最大path sum” ， “根val + 根右子最大path sum”， 根val， 这三者中的最大值。

递归函数原型为： helper(TreeNode root)

空间上是O(logn)递归栈的大小，时间上是O（n）

代码：

1. 
   
2. public class Solution {
   
3.     private int res;
   
4.     public int maxPathSum(TreeNode root) {
   
5.        res = Integer.MIN_VALUE;
   
6.        helper(root);
   
7.        return res;
   
8.     }
   
9.    
   
10.     public int helper(TreeNode root)
    
11.     {
    
12.        if(root == null) return 0;
    
13.        int left = helper(root.left);
    
14.        int right = helper(root.right);
    
15.        int cur = Math.max(root.val, Math.max(root.val + left, root.val + right));
    
16.        res = Math.max(res, Math.max(cur, root.val + left + right));
    
17.        return cur;
    
18.     }
    
19. }
    

复制代码

MengMa

Binary Tree Postorder Traversal （Recursion）

三种做法啊，由易到难的排序是： 递归，迭代， Morris

1。递归：
空间 O（logn）, 时间 O（n）
代码：

1. public class Solution {
   
2.     private ArrayList<Integer> res = new ArrayList<Integer>();
   
3.     public ArrayList<Integer> postorderTraversal(TreeNode root) {
   
4.         helper(root);
   
5.         return res;
   
6.     }
   
7.     private void helper(TreeNode root)
   
8.     {
   
9.         if(root == null) return;
   
10.         helper(root.left);
    
11.         helper(root.right);
    
12.         res.add(root.val);
    
13.     }
    
14. }

复制代码

MengMa

Binary Tree Postorder Traversal （Iteration 1）

2. 迭代：
有两种迭代做法： 本质上改变树结构的迭代。不改变树结构的迭代。
2.1 改变树结构的迭代。
这个方法比较好理解，但是缺点是树的结构被改变了。貌似LeetCode 没有对是否改变树结构进行检查，下面这段代码也能AC。对于当前栈顶元素，观察该节点是否有左子或右子，有则分别push，同时把栈顶元素的左子右子设为null.  说明再次遇到该节点时可以直接pop了。

1. public class Solution {
   
2.     public ArrayList<Integer> postorderTraversal(TreeNode root)
   
3.     {
   
4.         ArrayList<Integer> result = new ArrayList<Integer>();
   
5.         if(root == null) return result;
   
6.         LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
   
7.         stack.push(root);
   
8.         while(!stack.isEmpty())
   
9.         {
   
10.             TreeNode curNode = stack.peek();
    
11.            
    
12.             if(curNode.right!= null)
    
13.                 stack.push(curNode.right);
    
14.             
    
15.              if(curNode.left!= null)
    
16.                 stack.push(curNode.left);
    
17.             
    
18.             curNode.left = null;
    
19.             curNode.right = null;
    
20.             curNode = stack.peek();
    
21.             
    
22.             if(curNode.left == null && curNode.right == null)
    
23.             {
    
24.                 result.add(curNode.val);
    
25.                 stack.pop();
    
26.             }
    
27.         }
    
28.         return result;
    
29.     }
    
30. }

复制代码

如果必须不改变树的结构，可以先对树进行复制 （O(logn), O(n)）
再对tree的copy进行后续遍历。

copy树的代码

1. public static TreeNode copy(TreeNode root){  
   
2.         if(root == null){  
   
3.             return null;  
   
4.         }  
   
5.          
   
6.         TreeNode newNode = new TreeNode(root.val);  
   
7.         newNode.left = copy(root.left);  
   
8.         newNode.right = copy(root.right);  
   
9.          
   
10.         return newNode;  
    
11.     }  

复制代码

MengMa

Binary Tree Postorder Traversal （Iteration 2）
不改变树结构

这个应该是常用的解法。
1）如果当前栈顶元素的右结点存在并且还没访问过（也就是右结点不等于上一个访问结点），那么就把当前结点移到右结点继续循环；
2）如果栈顶元素右结点是空或者已经访问过，那么说明栈顶元素的左右子树都访问完毕，应该访问自己继续回溯了。
时间 O(n) 空间 O（logn）

1. public class Solution {
   
2.     public ArrayList<Integer> postorderTraversal(TreeNode root)
   
3.     {
   
4.         ArrayList<Integer> res = new ArrayList<Integer>();
   
5.         if(root == null) return res;
   
6.         LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
   
7.         TreeNode pre = null;
   
8.         while(root != null || !stack.isEmpty())
   
9.         {
   
10.            if(root != null)
    
11.            {
    
12.                stack.push(root);
    
13.                root = root.left;
    
14.            }
    
15.            else
    
16.            {
    
17.                TreeNode peekNode = stack.peek();
    
18.                if(peekNode.right != null && pre != peekNode.right)
    
19.                {
    
20.                    root = peekNode.right;
    
21.                }
    
22.                else
    
23.                {
    
24.                    stack.pop();
    
25.                    res.add(peekNode.val);
    
26.                    pre = peekNode;
    
27.                }
    
28.            }
    
29.         }
    
30.         return res;
    
31.     }
    
32. }

复制代码

jiejue

1. public class Solution {
   
2.     public boolean isBalanced(TreeNode root) {
   
3.         if (root == null) return true;
   
4.         if (Math.abs(lengthTree(root.left) - lengthTree(root.right)) <= 1)
   
5.         return isBalanced(root.left) && isBalanced(root.right);
   
6.         else return false;
   
7.     }
   
8.     public int lengthTree(TreeNode root)
   
9.     {
   
10.         if (root == null) return 0;
    
11.         if (root.left == null && root.right == null) return 1;
    
12.         if (root.left == null ) return lengthTree(root.right) + 1;
    
13.         if (root.right == null) return lengthTree(root.left) + 1;
    
14.         return Math.max(lengthTree(root.left),lengthTree(root.right)) + 1;
    
15.     }
    
16. }

复制代码

单独写了个求深度的函数。比楼主的要繁琐些。。。

补充内容 (12-9-2014 05:19 AM):
原来我要积分50才能看汇总贴里面的代码。。。好难攒分的说

freshwind

原来这个空间复杂度是O(logn)， 学习了。

1. class Solution {
   
2. public:
   
3.     bool isBalanced(TreeNode *root) {
   
4.         int level;
   
5.         return helper(root, level);
   
6.     }
   
7.     bool helper(TreeNode *root, int &level) {
   
8.         if (!root) {
   
9.             level = 0;
   
10.             return true;
    
11.         }
    
12.         int left_level;
    
13.         int right_level;
    
14.         if (!helper(root->left, left_level)) return false;
    
15.         if (!helper(root->right, right_level)) return false;
    
16.         if (abs(left_level - right_level) > 1) return false;
    
17.         level = max(left_level, right_level)+1;
    
18.         return true;
    
19.     }
    
20. };

复制代码