leetcode116. 填充每个节点的下一个右侧节点指针

leetcode116. 填充每个节点的下一个右侧节点指针

三月 14, 2020

leetcode116. 填充每个节点的下一个右侧节点指针

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

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

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

在这里插入图片描述

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]

我的思路

dfs遍历每个节点，把左右子节点全都连上。最后只剩下左树的最右边和右树的最左边，也就是上图的5和6.用一次循环解决他们的连接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    //public Node tmp=null;
    public Node connect(Node root) {
        if(root==null)return null;
        root.next=null;
        Node left=connect(root.left);
        Node right=connect(root.right);
        if(left!=null&&right!=null)
            left.next=right;
        traverse(left,right);
       
        return root;
    }
    public void traverse(Node root1,Node root2){
        if(root1==null)return ;
        while(root1.right!=null){
            root1.right.next=root2.left;
            root1=root1.right;
            root2=root2.left;
        }
    }
}

评论区的解法

这个想法挺神奇的，我也试过用next找下一个数，但是怎么也不对。也就是说先把左右儿子连上，再向下遍历，这样遍历左右儿子的时候，next就存在了，就可以通过next找到下一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public Node connect(Node root) {
        if(root == null || root.left == null) 
            return root;
        root.left.next = root.right;
        if(root.next != null){
            root.right.next = root.next.left;
        }
        connect(root.left);
        connect(root.right);
        return root;
    }
}

leetcode 38/100