二叉树:填充每个节点的下一个右侧节点指针(java)

这篇具有很好参考价值的文章主要介绍了二叉树:填充每个节点的下一个右侧节点指针(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

leetcode原题链接:

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

题目描述

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

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

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

二叉树:填充每个节点的下一个右侧节点指针(java)
输入:root = [1,2,3,4,5,6,7]
输出:[1,#,2,3,#,4,5,6,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,‘#’ 标志着每一层的结束。

示例2
输入:root = []
输出:[]

提示:
树中节点的数量在 [0, 212 - 1] 范围内
-1000 <= node.val <= 1000

进阶:
你只能使用常量级额外空间。
使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。

递归解法一

解题思路:
这题在递归中,主要思考点就是,递归左树和右树时。不是同一个头节点的子树时,怎么样把左树链接到右树上去。如上图中五和六节点在递归过程中,这两个点,并没在同一个递归过程中。就无法链接起来,因此我们要修改下递归过程,把左右树同时递归,这样在同一个过程里,就可以看见兄弟节点了。代码演示如下。

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

    public void process(Node root1,Node root2){
        if(root1 == null || root2 == null){
            return ;
        }
        root1.next = root2;
        //左树内部链接起来。
        process(root1.left,root1.right);
        //右树内部链接起来
        process(root2.left,root2.right);
        //左树和右树链接起来。
        process(root1.right,root2.left);
      
    }

递归方法二(效率更高)

思路:
我们在递归的过程中,把层级结构也进行递归,每次把层级结构和左树的右节点放进map 中,在遍历到右树时,根据层级来判断,拿到左树,然后把它们相连,就完成了递归。和上面相比,少了一次递归。效率会增加很多.代码演示。

class Solution {
    HashMap<Integer,Node>map = new HashMap();
    public Node connect(Node root) {
        if(root == null){
            return root;
        }
        process(root,0);
        return root;
    }


    public void process(Node root,int level){
        if(root == null || root.left == null){
            return;
        }
        root.left.next = root.right;
        v6(root.left,level + 1);
        v6(root.right,level + 1);
        if(map.get(level) != null){
            Node cur = map.get(level);
            cur.next = root.left;
        }
        map.put(level,root.right);
    }

}

二叉树专题

从前序与中序遍历序列构造二叉树(java)

leetcode二叉树中的最大路径和(java)

二叉树的递归–判断二叉树是否是满二叉树(java实现)文章来源地址https://www.toymoban.com/news/detail-468454.html

到了这里,关于二叉树:填充每个节点的下一个右侧节点指针(java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【每日一题】填充每个节点的下一个右侧节点指针 II

    【BFS】【树】【2023-11-03】 117. 填充每个节点的下一个右侧节点指针 II 为二叉树中的每一个节点填充下一个节点。 本题题目意思明确,我们只需要遍历二叉树每一层的节点,将节点的 next 指针指向同一层的下一个节点即可,属于二叉树层序遍历的基础题。 实现代码 复杂度分

    2024年02月05日
    浏览(40)
  • leetcode做题笔记116. 填充每个节点的下一个右侧节点指针

    给定一个  完美二叉树  ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下: 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为  NULL 。 初始状态下,所有 next 指针都被设置为  NULL 。

    2024年02月10日
    浏览(44)
  • 力扣:117. 填充每个节点的下一个右侧节点指针 II(Python3)

    给定一个二叉树: 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为  NULL  。 初始状态下,所有 next 指针都被设置为  NULL  。 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 示

    2024年02月07日
    浏览(45)
  • 【教3妹学编程-算法题】117. 填充每个节点的下一个右侧节点指针 II

    2哥 : 3妹,听说你昨天去面试了,怎么样啊? 3妹 :嗨,别提了,让我回去等通知,估计是没有通知了, 还浪费我请了一天假。 2哥 : 你又请假了啊, 你是怎么跟你那个严厉的老板请假的。 3妹 :我说我2哥生病了,嘿嘿~ 2哥 :一猜就是说我生病了,自从你找工作,我这一年

    2024年02月05日
    浏览(44)
  • 117.填充每个节点的下一个右侧节点 II

    ​​ 题目来源:         leetcode题目,网址:117. 填充每个节点的下一个右侧节点指针 II - 力扣(LeetCode) 解题思路:        按层遍历时修改 next 指针即可,每一层除最后一个元素 的next 指针指向空外,皆指向同层下一个元素。 解题代码: 总结:         官方题解给出了

    2024年02月06日
    浏览(44)
  • 2023-05-10:给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表 如果在二叉树中,存在一条一直向下的路径 且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值,

    2023-05-10:给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表 如果在二叉树中,存在一条一直向下的路径 且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值,那么请你返回 True 否则返回 False 。 一直向下的路径的意思是:从树中某个节点开始,一直连

    2024年02月03日
    浏览(47)
  • 面试算法53:二叉搜索树的下一个节点

    给定一棵二叉搜索树和它的一个节点p,请找出按中序遍历的顺序该节点p的下一个节点。假设二叉搜索树中节点的值都是唯一的。例如,在图8.9的二叉搜索树中,节点8的下一个节点是节点9,节点11的下一个节点是null。 解决这个问题的最直观的思路就是采用二叉树的中序遍历

    2024年02月06日
    浏览(38)
  • 寻找二叉树一个节点的后继节点

    后继节点:中序遍历的后一个节点 普通二叉树:中序遍历得到一个list,时间复杂度O(n) 本题的二叉树:有父节点的指针,后继节点与原节点的距离为1, 因此可以直接通过父节点找到下一个节点 优化:节点到另一个节点的真实距离为k,时间复杂度为O(k) 情况分析: 情况一:

    2024年02月08日
    浏览(33)
  • 假设二叉树中每个结点值为单个字符,采用二叉链存储结构存储。设计一个算法,求二叉树b中第k层上叶子结点个数(非递归算法)。

    int LevelCount(BiTNode *b,int k){         BiTNode *p=b,*temp[Maxsize];         int layer=0,count=0, m=0, n=1; (m: 上一层结点的尾   n: 当层结点的尾 )         temp[0]=NULL;         temp[1]=p;         if(p==NULL) return 0;// 二叉树为空,任意层结点个数均为 0         while(1){          

    2024年02月04日
    浏览(50)
  • 【数据结构】二叉树的节点总个数、叶子节点个数、第K层节点个数、二叉树的深度

    目录 1.结点总个数 1.1 局部静态变量法 思维 代码 不足之处 2.传指针法 程序代码 3.递归法 思想 程序代码 详细过程 2.叶子节点个数 思想 程序代码 3.第K层节点个数 思想 程序代码 4.二叉树深度 思想 程序代码         求二叉树节点总个数、叶子节点个数、第k层节点个数、二叉

    2024年02月02日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包