讨论/《二叉树》 - 填充每个节点的下一个右侧节点指针/
《二叉树》 - 填充每个节点的下一个右侧节点指针
共 14 个回复

Java 递归 0ms
无需多言,代码很简单

class Solution {
    public Node connect(Node root) {
        if(root!=null)dfs(root.left,root.right);
        return root;
    }
    void dfs(Node left,Node right){
        if(left==null||left.next==right)return;
        left.next=right;
        dfs(left.left,left.right);
        dfs(left.right,right.left);
        dfs(right.left,right.right);
    }
}
14

1,BFS解决

看到关于二叉树的问题,首先要想到关于二叉树的一些常见遍历方式,
对于二叉树的遍历有

  1. 前序遍历
  2. 中序遍历
  3. 后续遍历
  4. 深度优先搜索(DFS)
  5. 宽度优先搜索(BFS)

除了上面介绍的5种以外,还有Morris(莫里斯)的前中后3种遍历方式,总共也就这8种。所以只要遇到二叉树相关的算法题,首先想到的就是上面的几种遍历方式,然后再稍加修改,基本上也就这个套路。

这题让求的就是让把二叉树中每行都串联起来,对于这道题来说最适合的就是BFS。也就是一行一行的遍历,遍历的时候顺便把他们给串起来,如下图所示

image.png

二叉树BFS的代码如下

    public void levelOrder(TreeNode tree) {
        if (tree == null)
            return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(tree);//相当于把数据加入到队列尾部
        while (!queue.isEmpty()) {
            //poll方法相当于移除队列头部的元素
            TreeNode node = queue.poll();
            System.out.println(node.val);
            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
    }

在遍历每一行的时候,只要把他们串联起来就OK,下面就来把上面的代码改造一下

    public Node connect(Node root) {
        if (root == null)
            return root;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            //每一层的数量
            int levelCount = queue.size();
            //前一个节点
            Node pre = null;
            for (int i = 0; i < levelCount; i++) {
                //出队
                Node node = queue.poll();
                //如果pre为空就表示node节点是这一行的第一个,
                //没有前一个节点指向他,否则就让前一个节点指向他
                if (pre != null) {
                    pre.next = node;
                }
                //然后再让当前节点成为前一个节点
                pre = node;
                //左右子节点如果不为空就入队
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
        }
        return root;
    }

看一下运行结果
image.png


上面运行效率并不是很高,这是因为我们把节点不同的入队然后再不停的出队,其实可以不需要队列,每一行都可以看成一个链表比如第一行就是只有一个节点的链表,第二行是只有两个节点的链表(假如根节点的左右两个子节点都不为空)……

image.png
image.png

经过上面的几步,很容易把链表给串起来,最后再来看下代码

    public Node connect(Node root) {
        if (root == null)
            return root;
        //cur我们可以把它看做是每一层的链表
        Node cur = root;
        while (cur != null) {
            //遍历当前层的时候,为了方便操作在下一
            //层前面添加一个哑结点(注意这里是访问
            //当前层的节点,然后把下一层的节点串起来)
            Node dummy = new Node(0);
            //pre表示下一层节点的前一个节点
            Node pre = dummy;
            
            //然后开始遍历当前层的链表
            //因为是完美二叉树,如果有左子节点就一定有右子节点
            while (cur != null && cur.left != null) {
                //让pre节点的next指向当前节点的左子节点,也就是把它串起来
                pre.next = cur.left;
                //然后再更新pre
                pre = pre.next;

                //pre节点的next指向当前节点的右子节点,
                pre.next = cur.right;
                pre = pre.next;
                //继续访问这一行的下一个节点
                cur = cur.next;
            }
            //把下一层串联成一个链表之后,让他赋值给cur,
            //后续继续循环,直到cur为空为止
            cur = dummy.next;
        }
        return root;
    }

看一下运行结果,这种实现方式无论是执行时间还是内存消耗都比较满意
image.png


2,其他方式解决

上面两种方式都是参照117. 填充每个节点的下一个右侧节点指针 II的题解,第117题不是完美二叉树,所以第117题的答案都可以拿到这里来用,但这里的答案却不能全部用在第117题。

我们还可以参照上面的方式来修改一下

    public Node connect(Node root) {
        if (root == null)
            return null;
        Node pre = root;
        Node cur = null;
        while (pre.left != null) {
            //遍历当前这一层的结点,然后把他们的下一层连接起来
            cur = pre;
            //cur不为空,就表示这一层还没遍历完,就继续循环
            while (cur != null) {
                //让下一层的左子节点指向右子节点
                cur.left.next = cur.right;
                //如果cur.next不为空,就表示还没遍历到这一层
                //最后的那个节点的右子节点,就让前一个结点的右
                //子节点指向下一个节点的左子节点
                if (cur.next != null)
                    cur.right.next = cur.next.left;
                //然后继续连接下一个节点的 子节点
                cur = cur.next;
            }
            //继续下一层
            pre = pre.left;
        }
        return root;
    }

看一下运行结果
image.png


3,递归方式

或者也可以改为递归的 方式

    public Node connect(Node root) {
        dfs(root, null);
        return root;
    }

    private void dfs(Node curr, Node next) {
        if (curr == null)
            return;
        curr.next = next;
        dfs(curr.left, curr.right);
        dfs(curr.right, curr.next == null ? null : curr.next.left);
    }

看一下有运行结果
image.png


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

5

BFS迭代

public Node connect(Node root) {
        if(root==null)return root;
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size=queue.size();
            for (int i = 0; i <size ; i++) {
                Node node=queue.poll();
                if(i<size-1)node.next=queue.peek();
                if(node.left!=null)queue.offer(node.left);
                if(node.right!=null)queue.offer(node.right);
            }
        }
        return root;
}
3

利用对称二叉树的求解方法即可求解

class Solution {
public:
    void createConnect(Node* first, Node* second){
        if(first == NULL && second == NULL){
            return;
        }
        first->next = second;
        second->next = NULL;
        createConnect(first->left, first->right);
        createConnect(first->right, second->left);
        createConnect(second->left, second->right);
        createConnect(second->right, second->right);

    }
    Node* connect(Node* root) {
        if(root == NULL){
            return NULL;
        }
        if(root->left && root->right){
            createConnect(root, root);
        }
        return root;
    }
};
3

哦嘶!

class Solution {
public:
    Node* connect(Node* root) {
        if(root) helps(root);
        return root;
    }

    void helps(Node* &root){
        if(!root->left) return;
        root->left->next = root->right;
        if(root->next) root->right->next = root->next->left;
        helps(root->left);
        helps(root->right);
    }
};

广度优先搜索Java实现(类似之前的前序遍历,用队列)

public Node connect(Node root) {
        if(root==null)
           return null;   
        Queue<Node> q1 = new LinkedList<Node>();
        q1.add(root);
        while(q1.size()>0){
            int len = q1.size();
            for(int i = 0; i<len;i++){
                if(q1.peek().left!=null)
                   q1.add(q1.peek().left);
                if(q1.peek().right!=null)
                   q1.add(q1.peek().right);
                Node n1 = q1.poll();
                if(i<len-1)
                   n1.next = q1.peek();
                else
                   n1.next = null;
            }
        }
        return root;
    }
class Solution {
public:
    Node* connect(Node* root) {
        if(root==NULL) return root;
        queue<Node*> myqueue={};
        myqueue.push(root);
        while(!myqueue.empty())
        {
            Node* pos=NULL;
            int count=myqueue.size();
            for(int i=0;i<count;i++)
            {
                Node* cur=myqueue.front();
                myqueue.pop();
                if(i!=count-1)//如果没到一行的最后一个
                {
                    cur->next=myqueue.front();
                }
                if(cur->left)myqueue.push(cur->left);
                if(cur->right)myqueue.push(cur->right);
            }
        }
        return root;
    }
};

去掉这句操作会出现重复的递归,代码会从0ms掉到2ms

left.next==right
上述判断是不是可以去掉 有点冗余;

递归

关键是如何将同一层不同父节点的右左节点连接起来;
可以利用上一次递归的next找到相邻节点的父节点,然后设置next。

class Solution {
    public Node connect(Node root) {
        point(root);
        return root;
    }
    public void point(Node root){
        if(root==null||root.right==null) return;
        root.left.next=root.right;
        if(root.next!=null){
            root.right.next=root.next.left;
        }
        point(root.left);
        point(root.right);
    }
}