GuilinDev

Lc0116

05 August 2008

116 Populating Next Right Pointers in Each Node

原题概述

Given a binary tree

1
2
3
4
5

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to 

1

NULL
.

Initially, all next pointers are set to 

1

NULL
.

Note:

  • You may only use constant extra space.
  • Recursive approach is fine, implicit stack space does not count as extra space for this problem.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

Example:

Given the following perfect binary tree,

1
2
3
4
5

     1
   /  \
  2    3
 / \  / \
4  5  6  7

After calling your function, the tree should look like:

1
2
3
4
5

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

题意和分析

这道题是层序遍历的应用，找到每一层右边的结点，当遍历到一个节点时，处理该节点的左子树和右子树，这个处理的过程可以是递归或者非递归，两个方法都需要掌握。

代码

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        if (root.left == null) { //只有一个元素的情况
            root.next = null;
            return root;
        }
        return recursion(root);
    }
    private Node recursion(Node node) {
        if (node == null || node.left == null) { // 该层的下层为空，该层已经处理过
            return node; // return null;
        }
        node.left.next = node.right;
        node.right.next = (node.next == null) ? null : node.next.left;
        
        recursion(node.left);
        recursion(node.right);
        
        return node;
    }
}

非递归BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            // daga
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                // 当前层节点
                if (node.left != null) {
                    queue.offer(node.left);
                    node.left.next = node.right;
                }                
                
                if (node.right != null) {
                    queue.offer(node.right);
                    // 完美二叉树也需要处理最右边的节点，指向null
                    node.right.next = (node.next == null) ? null : node.next.left;
                }
            }            
        }
        return root;
    }
This site is open source. Improve this page.