前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 114. Flatten Binary Tree to Linked List

LeetCode 114. Flatten Binary Tree to Linked List

原创
作者头像
大学里的混子
修改2018-10-29 17:10:25
3350
修改2018-10-29 17:10:25
举报
文章被收录于专栏:LeetCode

114. Flatten Binary Tree to Linked List

代码语言:javascript
复制

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

    For example, given the following tree:

             1
            / \
           2   5
          / \   \
         3   4   6
    The flattened tree should look like:

            1
             \
              2
               \
                3
                 \
                  4
                   \
                    5
                     \
                      6

关于二叉树的题目,最直接最简单的方法就是采用递归,因为二叉树具有天然的递归结构,实际上二叉树的定义就是用递归的思想来定义的:一个节点的左右子树任然是一个二叉树。

解法一:

代码语言:txt
复制
    public void flatten(TreeNode root) {
        if (root ==null||(root.right==null&&root.left==null)) return;
        flatten(root.left);
        flatten(root.right);
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = null;
        TreeNode cur = root;
        while (cur.right!=null){
            cur =cur.right;
        }
        cur.right = temp;
    }

解法一的思路比较简单,但是要让左子树做flatten后的最后一个节点指向右子树做flatten操作后的第一个节点

,如何得到左子树做flatten后的最后一个节点呢?这就需要一个循环,上述代码中的:

代码语言:javascript
复制
         TreeNode cur = root;
        while (cur.right!=null){
            cur = cur.right;
        }

让cur记录左子树做flatten后的最后一个节点,这样增加了算法的复杂性,效率不是很高。

解法二:

思路:与解法一中的递归思路不一样,我们可以没每找到理论结果中的最后一个节点,再找理论结果中的倒数第二个节点,再倒数第三个………,依次类推,最后找到的是root节点。将写出以下的算法:

代码语言:javascript
复制
private TreeNode prev = null;
public void flatten(TreeNode root) {
    if (root == null)
        return;
    flatten(root.right);
    flatten(root.left);
    root.right = prev ;
    root.left = null;
    prev = root;
}

注意:这里的prev是一个全局变量,prev存的是上一次递归的root的结果。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 114. Flatten Binary Tree to Linked List
    • 解法一:
      • 解法二:
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档