Populating Next Right Pointers in Each Node (M)

題目

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *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 NULL.

Initially, all next pointers are set to NULL.

Example:

Input: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

Output: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

Note:

• You may only use constant extra space.
• Recursive approach is fine, implicit stack space does not count as extra space for this problem.

題意

對于滿二叉樹的每一層，將當前層每一個結點的next域指向該層的右邊一個結點；如果已經是當前層的最右結點，則指向null，(限制只能使用\(O(1)\)的額外空間，如果使用遞回，則系統堆疊不計入額外空間)

思路

如果不限制額外空間大小，最簡單的做法是層序遍歷處理，

兩種使用遞回的方法：

1. 遞回引數有兩個，分別是同一層上相鄰的兩個節點A和B，在完成連接 \(A.next = B\) 后，它們子樹的連接只有三種情況：\(A.left.next = A.right\)、\(A.right.next=B.left\)、\(B.left.next=B.right\)，所以只要遞回處理這三種情況即可，當然這種遞回方式存在重復連接的情況，因為同一個子樹可能被多次遞回訪問，
2. 遞回引數只有一個，即當前子樹的根節點x(x與它右邊兄弟結點的連接已經處理完畢)，如果x存在左子樹，由滿二叉樹的性質，則x一定存在右子樹，同時如果x存在兄弟結點y，則y也一定存在左子樹，將x的左子樹、右子樹和y的左子樹相連，就完成了本層遞回，接著繼續向x的左右子樹遞回即可，

另有一種只需要\(O(1)\)空間的迭代方法：
用head指向每一層的最左側結點，用cur從左到右遍歷(通過next連接)該層所有結點，在遍歷程序中將每個結點的左右子結點與右兄弟結點的左子結點相連，迭代head處理所有層，

代碼實作

Java

遞回1

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        
        connect(root.left, root.right);
        return root;
    }

    private void connect(Node x, Node y) {
        if (x == null || y == null) {
            return;
        }

        x.next = y;
        // 分三種情況處理子樹連接
        connect(x.left, x.right);
        connect(x.right, y.left);
        connect(y.left, y.right);
    }
}

遞回 2

class Solution {
    public Node connect(Node root) {
        rConnect(root);
        return root;
    }

    private void rConnect(Node x) {
        if (x == null) {
            return;
        }

        // 滿二叉樹的性質，如果存在左子樹則必然存在右子樹，且若存在兄弟結點，則兄弟結點也必存在左子樹
        if (x.left != null) {
            x.left.next = x.right;
            if (x.next != null) {
                x.right.next = x.next.left;
            }
        }

        rConnect(x.left);
        rConnect(x.right);
    }
}

層序遍歷(O(1)額外空間)

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }

        Node head = root;
        while (head.left != null) {
            Node cur = head;
            while (cur != null) {
                cur.left.next = cur.right;
                if (cur.next != null) {
                    cur.right.next = cur.next.left;
                }
                cur = cur.next;
            }
            head = head.left;
        }

        return root;
    }
}

層序遍歷(非O(1)額外空間)

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        
        Queue<Node> q = new ArrayDeque<>();
        q.offer(root);

        while (!q.isEmpty()) {
            int size = q.size();
            Node[] level = q.toArray(new Node[size]);
            for (int i = 0; i < size; i++) {
                if (i != size - 1) {
                    level[i].next = level[i + 1];
                }
                Node cur = q.poll();
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
        }
        
        return root;
    }
}

JavaScript

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function (root) {
  let q = []
  if (root) {
    q.push(root)
  }

  while (q.length) {
    let pre = null
    let size = q.length
    for (let i = 0; i < size; i++) {
      if (i == 0) {
        pre = q.shift()
      } else {
        let cur = q.shift()
        pre.next = cur
        pre = cur
      }
      if (pre.left) q.push(pre.left)
      if (pre.right) q.push(pre.right)
    }
  }
  return root
}

參考

cnBlogs - Grandyang

標籤：其他

上一篇：檔案匯編代碼中是如何確定函式的地址的呢？

下一篇：Mushroom Gnomes - 2 【CodeForces - 139E】