找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4455|回复: 15
收起左侧

[米群网刷题小分队] [LeetCode] Tree题目

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-8-2014 11:05 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-13-2014 02:13 PM 编辑

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

本帖被以下淘专辑推荐:

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-12-2014 08:29 PM | 显示全部楼层
本帖最后由 MengMa 于 12-13-2014 03:58 PM 编辑

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. }
复制代码



90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-12-2014 08:32 PM | 显示全部楼层
本帖最后由 MengMa 于 12-13-2014 12:04 AM 编辑

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. }
复制代码





90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-12-2014 08:32 PM | 显示全部楼层
本帖最后由 MengMa 于 12-12-2014 11:56 PM 编辑

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.     }
复制代码




90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-12-2014 10:22 PM | 显示全部楼层
本帖最后由 MengMa 于 12-13-2014 01:45 PM 编辑

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. public class Solution {
  2.     private int res;
  3.     public int maxPathSum(TreeNode root) {
  4.        res = Integer.MIN_VALUE;
  5.        helper(root);
  6.        return res;
  7.     }
  8.    
  9.     public int helper(TreeNode root)
  10.     {
  11.        if(root == null) return 0;
  12.        int left = helper(root.left);
  13.        int right = helper(root.right);
  14.        int cur = Math.max(root.val, Math.max(root.val + left, root.val + right));
  15.        res = Math.max(res, Math.max(cur, root.val + left + right));
  16.        return cur;
  17.     }
  18. }
复制代码


90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-13-2014 03:41 PM | 显示全部楼层
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. }
复制代码

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-13-2014 03:43 PM | 显示全部楼层
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.     }  
复制代码



90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-13-2014 03:55 PM | 显示全部楼层
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. }
复制代码



10

主题

1

精华

210

积分

高级会员

Rank: 3Rank: 3

积分
210
发表于 12-9-2014 05:19 AM | 显示全部楼层
  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才能看汇总贴里面的代码。。。好难攒分的说

18

主题

6

精华

257

积分

高级会员

Rank: 3Rank: 3

积分
257
发表于 12-9-2014 07:09 AM | 显示全部楼层
原来这个空间复杂度是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. };
复制代码
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表