找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1503|回复: 5
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Flatten Binary Tree to Linked List】-【刷题第一弹2014】

[复制链接]

7

主题

3

精华

195

积分

资深会员

Rank: 2

积分
195
发表于 10-22-2014 10:37 PM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 qiuchen 于 10-22-2014 10:50 PM 编辑

快速通道:
https://oj.leetcode.com/problems ... ree-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


常见解题思路:
一直往右走(没有左孩子)来模拟链表。老套路还是用递归来解决,维护先序遍历的前一个结点pre,然后每次把pre的左结点置空,右结点设为当前结点。这里需要注意的一个问题就是我们要先把右子结点保存一下,以便等会可以进行递归,否则有可能当前结点的右结点会被覆盖,后面就取不到了。


算法的复杂度:
time complexity: O(n); space complexity: O(logn).


Java Solution:

public void flatten(TreeNode root)     {
   ArrayList<TreeNode> pre = new ArrayList<TreeNode>();
   pre.add(null);
   helper(root, pre);
  }

private void helper(TreeNode root, ArrayList<TreeNode> pre)
{
   if(root == null) return;
   TreeNode right = root.right;
   if(pre.get(0)!=null)
    {
      pre.get(0).left = null;
      pre.get(0).right = root;
    }
   pre.set(0,root);
   helper(root.left, pre);
   helper(right, pre);
  }





本帖被以下淘专辑推荐:

7

主题

3

精华

195

积分

资深会员

Rank: 2

积分
195
 楼主| 发表于 10-22-2014 11:01 PM | 显示全部楼层
另外补充一个比较巧妙的解法:

Thoughts

Go down through the left, when right is not null, push right to stack.

Java Solution

/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
    public void flatten(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;

        while(p != null || !stack.empty()){

            if(p.right != null){
                stack.push(p.right);
            }

            if(p.left != null){
                p.right = p.left;
                p.left = null;
            }else if(!stack.empty()){
                TreeNode temp = stack.pop();
                p.right=temp;
            }

            p = p.right;
        }
    }
}
回复 支持 反对

使用道具 举报

8

主题

5

精华

1243

积分

顶级会员

Rank: 6Rank: 6

积分
1243

热心会员推广达人

发表于 11-11-2014 09:36 PM | 显示全部楼层
  1.     public void flatten(TreeNode root) {
  2.         if(root == null) return;
  3.         helper(root);
  4.     }
  5.     public TreeNode helper(TreeNode root){
  6.         if(root.left==null && root.right==null)
  7.             return root;
  8.         TreeNode tmp = null;
  9.         if(root.right!=null){
  10.             tmp = helper(root.right);
  11.         }
  12.         if(root.left!=null){
  13.             root.right = helper(root.left);
  14.             root.left = null;
  15.         }
  16.         TreeNode node = root;
  17.         while(node.right!=null && node.right!=tmp){
  18.             node = node.right;
  19.         }
  20.         node.right = tmp;
  21.         return root;
  22.     }
  23. 这题关键是思路吧,O(n)的time,是因为你每个node都要遍历到,O(logn)的递归stack空间,当然,这里思路和楼主一样,就是先往右走,当右边没有node就check下左边有没node,有就继续遍历左边,然后一直向右,关键也是记录右边修改好的node,这里用tmp来记录,然后一层层递归回去,有两点应该牢记,第一就是别忘记set左边node为null,第二就是递归的顺序,一直右,再左再一直右,然后记录  --------当然,这题也有变形,双向链表?我记得有人面indeed 考过
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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