专栏首页码上积木LeetCode题解—填充二叉树节点右侧指针

LeetCode题解—填充二叉树节点右侧指针

前言

今天继续看二叉树的算法:填充每个节点的下一个右侧节点指针

题目

给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。

解法一

题目什么意思呢?就是把完全二叉树的么一行用指针进行连接,类似这样:

      1  -> null
    /   \
   2  -> 3  -> null
  / \   / \
 4-> 5->6->7  -> null

所以我首先想到的办法就是遍历,用深度优先遍历每一层树结构,然后用集合存储再一一连接:

 public Node connect(Node root) {
  if(root==null) {
   return root;
  }
  //每一层都用queue保存
  LinkedList<Node> queue = new LinkedList<Node>();
  queue.add(root);
  //开始遍历树结构,当queue为空则遍历结束
  while(queue.size()>0) {
   int size = queue.size();
   //将列表的元素串联起来
   Node tmp = queue.get(0);
   for(int i=1;i<size;++i) {
    tmp.next = queue.get(i);
    tmp = queue.get(i);
   }
   //删除这一层树结构,并把树的下一层节点加到列表中
   for(int i=0;i<size;++i) {
    tmp = queue.remove();
    if(tmp.left!=null) {
     queue.add(tmp.left);
    }
    if(tmp.right!=null) {
     queue.add(tmp.right);
    }
   }
  }
  return root;
 }

这种解法就比较清晰,每次遍历树的一层结构,然后进行连接

复杂度

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

解法2

如果不用到单独的列表,也就是用常量级的空间可以完成这一题吗?

不用到列表辅助,如果一层只有两个节点,那么就可以写成:

root.left.next = root.right;

那对于一层多个节点,比如4个节点,8个节点的情况,就要垮父节点操作,这时候我们就要用到父节点的next进行遍历:

if (parenthead.next != null) {
    parenthead.right.next = parenthead.next.left;
}

所以,就能得出新的解法:

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        
        // 从根节点开始
        Node leftmost = root;
        
        //遍历每一层,直到没有下层节点
        while (leftmost.left != null) {
            
            Node head = leftmost;
            
            //遍历当前这一层
            while (head != null) {
                
                // 连接第一个小树
                head.left.next = head.right;
                
                // 链接第二个小树,根据父节点的next
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                
                // 指针向后移动
                head = head.next;
            }
            
            // 去下一层的最左的节点
            leftmost = leftmost.left;
        }
        
        return root;
    }
}

复杂度

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

解法3

还有一种解法,就是递归,我们可以设计一种递归方法,每次传入两个节点,并且相连:

void connectTwo(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return;
    }
    // 将传入的两个节点连接
    node1.next = node2;
}

然后调用递归方法的场景无非就是两个树结构,所以涉及到三种场景:

  • 树1的左节点连接右节点
  • 树1的右节点连接树2的左节点
  • 树2的左节点连接右节点

所以得出以下解法:

 public Node connect(Node root) {
        if(root==null) return null;
        connectTwo(root.left,root.right);
        return root;
    }

    public void connectTwo(Node root1,Node root2) {
        if(root1==null)return;
        root1.next=root2;

        connectTwo(root1.left,root1.right);
        connectTwo(root1.right,root2.left);
        connectTwo(root2.left,root2.right);
    }

还可以对第二种场景,也就是树1的右节点连接树2的左节点进行优化,将两颗树的处理放到递归方法里面:

public Node connect(Node root) {
        if(root==null) return null;
        connection(root);
        return root;
    }
    public void connection(Node root){
        if(root.left == null) return;
        root.left.next=root.right;
        if(root.next != null){
            root.right.next=root.next.left;
        }
        connection(root.left);
        connection(root.right);
    }

复杂度

假设树的高度为h。

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

参考

https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node https://labuladong.gitee.io

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

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 116: 填充每个节点的下一个右侧节点指针

    给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

    爱写bug
  • 【LeetCode两题选手】算法类题目(8.7)

    给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

    看、未来
  • 【Leetcode】117. 填充每个节点的下一个右侧节点指针 II

    struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 nex...

    Leetcode名企之路
  • ​LeetCode刷题实战116:填充每个节点的下一个右侧节点指针

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • LeetCode1-120题汇总,希望对你有点帮助!

    时间很快,公众号发布的LeetCode题目,已经达到120道题了。今天把发布的1-120篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相...

    程序IT圈
  • ​LeetCode刷题实战117:填充每个节点的下一个右侧节点指针 II

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

    程序IT圈
  • Python 刷题笔记:二叉树专题一

    今天来看二叉树专题,首先我们先整理下基础知识点;基于在 LeetCode 推荐题解中发现的一个适用于二叉树遍历的套路解法,我们今天也会连刷三道关于前序、中序和后...

    TTTEED
  • LeetCode117:填充每个节点的下一个右侧节点指针 II

    填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

    爱写bug
  • LeetCode 116. 填充每个节点的下一个右侧节点指针(递归&循环)

    给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

    Michael阿明
  • Leetcode | 第9节:树(下),数学题选摘

    这一节我们会继续上一节的最后,考虑树相关的问题。并且按照计划,我们会讲一些可能会考察到的数学题。

    学弱猹
  • LeetCode 117. 填充每个节点的下一个右侧节点指针 II(递归&循环)

    填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

    Michael阿明
  • 打卡群刷题总结0814——二叉树展开为链表

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

    木又AI帮
  • 【一天一大 lee】填充每个节点的下一个右侧节点指针 II (难度:中等) - Day20200928

    填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

    前端小书童
  • LeetCode 655. 输出二叉树(二叉树高度&二叉树遍历)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/print-binary-tree 著作权归领扣网络...

    Michael阿明
  • 二叉树问题(二)-LeetCode 965、563、993、958、919(树深度,层次遍历)

    如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时,才返回 true;否则返回 false。

    算法工程师之路
  • 二叉树问题(三)-LeetCode 669、951、662、199、538、236(中序,层次遍历)

    给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果...

    算法工程师之路
  • 【Leetcode】116. 填充同一层的兄弟节点

    给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

    Leetcode名企之路
  • 力扣 (LeetCode)-对称二叉树,树|刷题打卡

    每天学习编程,让你离梦想更新一步,感谢不负每一份热爱编程的程序员,不论知识点多么奇葩,和我一起,让那一颗四处流荡的心定下来,一直走下去,加油,2021加油!欢迎...

    达达前端
  • 【算法专栏】从上到下打印二叉树

    请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

    ConardLi

扫码关注云+社区

领取腾讯云代金券