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

题目描述

给定一个二叉树

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

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

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

解题思路

层次遍历

层次遍历可以很直接的实现题目中要求的操作，层次遍历基于广度优先搜索。

Code

class Solution{
    public Node connect(Node root){
        if(root == null){
            return null;
        }
        Queue<Node> tmp = new LinkedList<>();
        tmp.offer(root);
        while(!tmp.isEmpty()){
            int n = tmp.size();
            for(int i = 1;i <= n;i++){
                Node cur = tmp.poll();
                if(i != n){
                    cur.next = tmp.peek();
                }
                if(cur.left != null){
                    tmp.offer(cur.left);
                }
                if(cur.right != null){
                    tmp.offer(cur.right);
                }
            }
        }
        return root;
    }
}

复杂度分析

时间复杂度：O(N)。因为需要遍历树上所有的点，所以时间复杂度为O(N)。

空间复杂度：O(N)。队列的空间代价。