> LeetCode116. 填充每个节点的下一个右侧节点指针 - Yuyy
Yuyy
Yuyy
LeetCode116. 填充每个节点的下一个右侧节点指针

一、思路

经过画图发现,儿子之间连接没问题。但是不同父亲的孙子连接有问题,解决一个倒还好,巧妙的是经过递归,可以解决所有这类问题。
总是想着把问题分治,但分治完了却没想到可以还原回去。。。

二、问题

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

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

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

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

 

进阶:

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

 

示例:

https://assets.leetcode.com/uploads/2019/02/14/116_sample.png

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

 

提示:

  • 树中节点的数量少于 4096
  • -1000 <= node.val <= 1000
Related Topics
  • 深度优先搜索
  • 广度优先搜索
  • \n

  • 👍 404
  • 👎 0
  • 三、代码

    public Node connect(Node root) {
                if (root == null) {
                    return null;
                }
                convert(root.left, root.right);
                return root;
            }
    
            private void convert(Node left, Node right) {
                if (left == null || right == null) {
                    return;
                }
                left.next = right;
                convert(left.left, left.right);
                convert(right.left, right.right);
                convert(left.right, right.left);
            }
    
    没有标签
    首页      算法训练      LeetCode116. 填充每个节点的下一个右侧节点指针

    发表评论

    textsms
    account_circle
    email

    Yuyy

    LeetCode116. 填充每个节点的下一个右侧节点指针
    一、思路 经过画图发现,儿子之间连接没问题。但是不同父亲的孙子连接有问题,解决一个倒还好,巧妙的是经过递归,可以解决所有这类问题。 总是想着把问题分治,但分治完了却没想到可以…
    扫描二维码继续阅读
    2021-03-01
    友情链接
    标签
    文章归档
    近期文章