专栏首页LeetCodeLeetCode 114. Flatten Binary Tree to Linked List
原创

LeetCode 114. Flatten Binary Tree to Linked List

114. Flatten Binary Tree to Linked List

    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

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

解法一:

    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后的最后一个节点呢?这就需要一个循环,上述代码中的:

         TreeNode cur = root;
        while (cur.right!=null){
            cur = cur.right;
        }

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

解法二:

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

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的结果。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BST & AVL 二分搜索树 & 平衡二叉树的实现原理

    本文完整的实现了基本的BST,由于注重的是逻辑和原理的实现,所以没有采用泛型。注意方法的访问修饰符。

    大学里的混子
  • LeetCode 783 & 530 Distance Between BST Nodes

    Given a Binary Search Tree (BST) with the root node root, return the minimum dif...

    大学里的混子
  • LeetCode 832. Flipping an Image

    Given a binary matrix A, we want to flip the image horizontally, then invert it,...

    大学里的混子
  • 安装CDSW数据磁盘初始化异常问题分析

    本文主要讲述基于Kerberos环境下的CDH5.13.1版本安装CDSW1.3.0数据磁盘初始化异常问题分析及解决办法。

    Fayson
  • 【leetcode刷题】T129-翻转二叉树

    https://leetcode-cn.com/problems/invert-binary-tree/

    木又AI帮
  • leetcode226——翻转二叉树

    故事尾音
  • 禁止网页复制代码

    网页禁止右键、禁止查看源代码、禁止复制的代码,试试你的右键、ctrl+c和ctrl+c吧 <SCRIPT language=javascript type=te...

    似水的流年
  • 958. 二叉树的完全性检验

    输入:[1,2,3,4,5,null,7] 输出:false 解释:值为 7 的结点没有尽可能靠向左侧

    程序员小王
  • 【LeetCode】一文详解二叉树的三大遍历:前序、中序和后序(python和C++实现)

    深度学习技术前沿公众号博主
  • leecode刷题(24)-- 翻转二叉树

    二叉树问题,我们首先要想到的使用递归的方式来解决,有了这个思路,处理这道问题就很简单了:先互换根节点的左右节点,然后递归地处理左子树,再递归地处理右子树,直到所...

    希希里之海

扫码关注云+社区

领取腾讯云代金券