专栏首页码上积木二叉树小结及习题—展开为链表

二叉树小结及习题—展开为链表

前言

新文章还没有准备好,所以先来一篇算法咯,嘿嘿,新文章周一见。

今天继续说说二叉树的算法。

不知道大家有没有发现,二叉树的很多问题都会涉及到递归算法,今天就来小结一下。

小结

      1 
    /   \
   2     3  
  / \   / \
 4   5  6  7 

二叉树的遍历,一共有三种:前序、中序、后序。

  • 前序。代表每个树都会按照中间节点、左节点、右节点的方式排序,上述例子的前序排列就是:1、2、4、 5、 3、6、7
  • 中序。代表每个树都会按照左节点、中间节点、右节点的方式排序,上述例子的中序排列就是:4、2、5、 1、 6、3、7
  • 后序。代表每个树都会按照左节点、右节点、中间节点的方式排序,上述例子的后序排列就是:4、5、2、 6、7、3、 1

通过三种遍历情况,我们可以发现的共通点是:都是先左节点,后右节点,只是中间节点的位置不同。 所以综合一下,可以得出一种通用的二叉树遍历方法,是一种递归算法:

//二叉树的递归
void traverse(TreeNode root) {
 if (root==null) return
    traverse(root.left)
    traverse(root.right)
}

但是、这个递归跟我们的遍历方法有什么关系呢,也没看到具体的前序、中序、后序啊?

递归的精妙之处就在于,递和归是两个过程,而在不同的过程进行处理就会有不同的结果。

我们试着在递的过程中加入打印:

//二叉树的递归
void traverse(TreeNode root) {
 if (root==null) return

 // 前序遍历点
    System.out.println(root.val)

    traverse(root.left)
    traverse(root.right)
}

在方法开始进行节点打印,那么就会一路从左边打印下来:

  • traverse(1),traverse(2),traverse(4)
  • traverse(5)
  • traverse(3),traverse(6),traverse(7)

同样,在递和归直接打印节点就是中序遍历,在归阶段打印节点就是后序遍历,最后得出二叉树遍历的总结递归方法:

//二叉树的递归
void traverse(TreeNode root) {
    // 前序遍历点
    System.out.println(root.val)

    traverse(root.left)

    // 中序遍历点
    System.out.println(root.val)

    traverse(root.right)

    // 后序遍历点
    System.out.println(root.val)
}

以后遇到二叉树的问题就可以把这个递归方法作为基础进行延伸。

题目

再来个题目进行巩固:二叉树展开为链表

给你二叉树的根结点 root ,请你将它展开为一个单链表:

展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1:

输入:root = [1,2,5,3,4,null,6] 输出:[1,null,2,null,3,null,4,null,5,null,6]

题解

题目已经给出了链表的顺序就是先序遍历,所以我们可以先对二叉树进行先序遍历,保存到集合,然后再针对集合每个值的左右节点进行赋值(left->null, right-> 下个节点):

class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        preorderTraversal(root, list);
        int size = list.size();
        for (int i = 1; i < size; i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }

    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
        if (root != null) {
            list.add(root);
            preorderTraversal(root.left, list);
            preorderTraversal(root.right, list);
        }
    }
}

再结合我们刚才的小结,通过递归方法就可以完成先序遍历,然后再一个个进行前后指针赋值就可以了。

这样看是不是挺简单的?

复杂度

时间复杂度:O(n) 空间复杂度:O(n)

题解2

还有没有其他的解法呢?

我们在回顾下前序的规律:

中间节点、左节点、右节点

所以对于某个节点来说,其右子树肯定在左子树的后面,而左子树中的最后一个节点就是左子树中最右边的节点,这个节点也就是右子树的前驱节点,来个图:

      1 
    /   \
   2     3  
  / \     \
 4   5     7 

对于根节点1,3子树的前驱节点就是2子树最右边的节点,也就是5。

所以我们可以把3子树作为5这个链表节点的下一个指针指向。

这样一个个节点处理完之后,链表结构就出来了,比如上述的例子:

  • 第一步:把5作为3子树的前驱节点。
  • 第二步:把2子树作为1的右子树

就变成了:

  1     
   \   
   2    
  / \  
 4   5 
     \ 
      3    
      \  
       7
  • 第三步:把4作为5子树的前驱节点

继续遍历,直到最后一个节点7,都没有左子树了,完成解法。

贴上代码:

class Solution {
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
         //判断还有没有右子树
            if (curr.left != null) {
             //判断还有没有左子树
                TreeNode next = curr.left;
                TreeNode predecessor = next;
                while (predecessor.right != null) {
                 //找到左子树中最右边的节点
                    predecessor = predecessor.right;
                }
                //作为前驱节点
                predecessor.right = curr.right;
                //重新赋值右子树
                curr.left = null;
                curr.right = next;
            }
            //继续遍历
            curr = curr.right;
        }
    }
}

复杂度

时间复杂度:O(n) 空间复杂度:O(1)

参考

https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

感谢大家的阅读,有一起学习的小伙伴可以关注下公众号—码上积木❤️ 每日一个知识点,建立完整体系架构。

本文分享自微信公众号 - 码上积木(Lzjimu),作者:积木zz

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetCode182|二叉树展开为链表

    码农王同学
  • 114. 二叉树展开为链表

    CaesarChang张旭
  • 【Leetcode】114. 二叉树展开为链表

    这算是比较经典的一道题目了, 博主面试快手的时候原题。最开始一想,觉得递归的求解不就好了,但是递归的时候发现需要注意一个地方就是:需要先递归右子树,然后记录下右...

    Leetcode名企之路
  • 打卡群刷题总结0814——二叉树展开为链表

    链接:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node

    木又AI帮
  • 打卡群刷题总结0813——二叉树展开为链表

    链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

    木又AI帮
  • ​LeetCode刷题实战114:二叉树展开为链表

    https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

    程序IT圈
  • 【LeetCode】每日一题(8.2)二叉树展开为链表

    具体做法是,对于当前节点,如果其左子节点不为空,则在其左子树中找到最右边的节点,作为前驱节点,将当前节点的右子节点赋给前驱节点的右子节点(其实就是找左子节点的最...

    看、未来
  • Leetcode算法【114. 二叉树展开为链表】

    上周通过一位小伙伴,加入了一个氛围很好的小群,人不多,但是大家保持着对知识的渴望,让我很感动。

    程序员小跃
  • LeetCode 114. 二叉树展开为链表(递归)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-link...

    Michael阿明
  • [Leetcode][python]Flatten Binary Tree to Linked List/二叉树展开为链表

    把一棵二叉树变为链表(扁平化),也就是一棵所有节点要么没有子节点,要么只有右节点的二叉树。

    蛮三刀酱
  • 114. 二叉树展开为链表 Krains 2020-08-02 08:59:00 树

    Krains
  • 一天一大 leet(二叉树展开为链表)难度:中等-Day20200802

    前端小书童
  • Day68:剑指Offer总结

      本人花了两个月时间刷完了牛客网带上的剑指Offer,一共67题。本人是从4月21日开始刷题,每天一题,截止到7月6日已经全部刷完。这67题均是考察的数据结构...

    一计之长
  • Android工程师面试字节力扣刷题没有针对性?常见数据结构与算法面试题合集整出来了!

    对于移动开发者来说,面试字节跳动最重要出了Android相关的面试题外算法是最重要的,而字节也非常喜欢在每面的最后问几个算法相关的问题,很多Android程序员...

    Android技术干货分享
  • 算法学习笔记

    这是一个算法题目合集,题目是我从网络和书籍之中整理而来,部分题目已经做了思路整理。问题分类包括:

    芋道源码
  • Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

    瑞士计算机科学家Niklaus Wirth在1976年写了一本书,名为《算法+数据结构=编程》。

    JAVA高级架构开发
  • 与机器学习算法有关的数据结构

    可能你对经常使用的统计分类包中的功能不满足你的需求而感到不爽,或者你已经有了一个新的数据处理方法。所以,你决定改动现有封装好的算法,开始编写你自己的机器学习方法...

    Hondsome
  • 打牢算法基础,从动手出发!

    大家好,我是光城。算法在计算机领域的重要性,就不用我多说了,每个人都想要学算法,打牢算法基础,可是不知道如何做,今天我来推荐一波学习思路。

    公众号guangcity
  • 代码面试需要知道的8种数据结构(附面试题及答案链接)

    为了保证可读性,本文采用意译而非直译。另外,本文版权归原作者所有,翻译仅用于学习。

    Fundebug

扫码关注云+社区

领取腾讯云代金券