Populating Next Right Pointers in Each Node II (M)

題目

Given a binary tree

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":null,"next":null,"right":{"$id":"6","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":null,"right":null,"val":7},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"6","left":null,"next":null,"right":{"$ref":"5"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"6"},"val":1}

Explanation: Given the above 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)\)的額外空間，如果使用遞回，則系統堆疊不計入額外空間)

思路

與 116. Populating Next Right Pointers in Each Node 相比，只是在滿二叉樹這個條件上做了變化，因此只要在先前的代碼上做出修改即可，

代碼實作

Java

遞回

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

        // 尋找root的右兄弟子樹中出現的第一個子結點
        Node p = root.next;
        while (p != null) {
            if (p.left != null) {
                p = p.left;
                break;
            }
            if (p.right != null) {
                p = p.right;
                break;
            }
            p = p.next;
        }

        if (root.right != null) {
            root.right.next = p;
            p = root.right;
        } 
        if (root.left != null) {
            root.left.next = p;
        }

        // 注意需要先遞回右子樹再遞回左子樹，具體原因見參考評論
        connect(root.right);
        connect(root.left);

        return root;
    }
}

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

// 版本1
class Solution {
    public Node connect(Node root) {
        Node head = root;

        while (head != null) {
            Node nextHead = null;		// 指向下一層的第一個結點
            Node last = null;			// 指向下一層已連接的最后一個結點
            
            // 連接下一層所有結點
            while (head != null) {
                if (head.left != null) {
                    if (nextHead == null) {
                        nextHead = head.left;
                        last = nextHead;
                    } else {
                        last.next = head.left;
                        last = last.next;
                    }
                }
                if (head.right != null) {
                    if (nextHead == null) {
                        nextHead = head.right;
                        last = nextHead;
                    } else {
                        last.next = head.right;
                        last = last.next;
                    }
                }
                head = head.next;
            }
            
            head = nextHead;
        }

        return root;
    }
}

// 版本2
class Solution {
    public Node connect(Node root) {
        Node dummy = new Node(0, null, null, null);
        Node cur = dummy;
        Node head = root;
        
        while (root != null) {
            if (root.left != null) {
                cur.next = root.left;
                cur = cur.next;
            }
            if (root.right != null) {
                cur.next = root.right;
                cur = cur.next;
            }
            root = root.next;
            if (root == null) {
                root = dummy.next;
                cur = dummy;
                dummy.next = null;
            }
        }

        return head;
    }
}

JavaScript

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function (root) {
  let p = root

  while (p) {
    let first = null
    let last = null

    while (p) {
      if (p.left && !first) {
        first = p.left
        last = p.left
      } else if (p.left) {
        last.next = p.left
        last = p.left
      }
      if (p.right && !first) {
        first = p.right
        last = p.right
      } else if (p.right) {
        last.next = p.right
        last = p.right
      }
      p = p.next
    }

    p = first
  }

  return root
}

參考

cnBlogs - Grandyang

標籤：其他

上一篇：最短路徑問題——分支限界法

下一篇：Unity周記: 2020.11.30-12.06