LeetCode Populating Next Right Pointers in Each Node

· 689 words · 2 minute read
2017年7月
LeetCode

117. Populating Next Right Pointers in Each Node II

Follow up for problem “Populating Next Right Pointers in Each Node”.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

  • You may only use constant extra space.

For example,

Given the following binary tree,

     1
   /  \
  2    3
 / \    \
4   5    7

After calling your function, the tree should look like:

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

方法

一看到此题，想当然需要进行层次遍历，但是额外空间只能是常数，说明不能用队列来对所有的节点进行存储，那该怎么办呢？

此题的解法给了我对于树中这种类型题目解题的一个很好的思路。新开辟一个节点,用这个新开辟的节点来进行层次遍历，每到下一层时，原先新开辟节点的next都不要，重新开始做next,具体步骤如下：

  1. 新开辟节点tl，使用tl来存储同一层节点的next关系 TreeLinkNode tl = new TreeLinkNode(0);
  2. 对于当前root,使用新开辟的节点tl来存储root的left指向right的关系，由于节点的赋值只是将节点的地址复制到另外一个节点，因此使用tl来存储next关系时，树中也就存在了next关系
  3. 当root == null时，说明一层已经遍历完了，需要到下一层，遍历下一层第一个节点就是tl的第一个next,因此将root = tl.next，重新开始做tl的next遍历，因此将之前的tl.next设置为null。

本题给我新的思路就是:对于树的问题，在已有的left和right关系下，若要新增关系，且规定只能新建常数个节点，则可以新建一个节点，该节点专门做满足新增关系的操作，由于节点的赋值只是地址赋值，因此满足新的关系并不会使原先已有的关系消失！！！

    /**
     * Definition for binary tree with next pointer.
     * public class TreeLinkNode {
     *     int val;
     *     TreeLinkNode left, right, next;
     *     TreeLinkNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public void connect(TreeLinkNode root) {
            TreeLinkNode tl = new TreeLinkNode(0);
            TreeLinkNode pre = tl;
            while(root != null){
                if(root.left != null){
                    pre.next = root.left;
                    pre = pre.next;
                }
                if(root.right != null){
                    pre.next = root.right;
                    pre = pre.next;
                }
                root = root.next;
                if(root == null){
                    pre = tl;
                    root = tl.next;
                    tl.next = null;
                }
            }

        }
    }
Share