Populating Next Right Pointers in Each Node II-K6K4.com

原题： https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/description/

题意： 题"Populating Next Right Pointers in Each Node"的进阶，给定的二叉树是任意二叉树。

约定：（1）要求使用O(1)的空间复杂度。

例子：

给定：
        1
       /  \
      2    3
     / \    \
    4   5    7
返回：
        1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

标签： pointers、populating、node、ii、进阶、面试

猜你感兴趣的圈子：

LeetCode交流圈

Bingo

2017-08-13 09:57:18 1楼#1层

Java三指针法：

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null) return;
        TreeLinkNode p = root;
        TreeLinkNode first = null;
        //上一个节点，我们给上一个节点的next赋值，然后再更新上一个节点为它的next
        TreeLinkNode last = null;
        while(p != null){
            //下一层的头节点有可能是左子节点也有可能是右子节点
            if(first == null){
                if(p.left != null){
                    first = p.left;
                } else if(p.right != null){
                    first = p.right;
                }
            }
            //更新last和last的next
            if(p.left != null){
                if(last != null){
                    last.next = p.left;
                }
                last = p.left;
            }
            if(p.right != null){
                if(last != null){
                    last.next = p.right;
                }
                last = p.right;
            }
            //如果当前节点没有next，则该层结束，转入下一层，否则就继续
            if(p.next != null){
                p = p.next;
            } else {
                p = first;
                first = null;
                last = null;
            }
            
        }
    }
}

Bingo

2017-08-13 09:57:47 2楼#1层

Java层次递进法：

public class Solution {
    public void connect(TreeLinkNode root) {
        // head是上一层的节点，我们用上一层节点的next形成链表，来链接当前这层
        TreeLinkNode head = root;
        while(head != null){
            // 记录链接到哪个节点的额外指针
            TreeLinkNode curr = new TreeLinkNode(0);
            // tmp指向该层的第一节点
            TreeLinkNode tmp = curr;
            while(head != null){
                // 尝试链接左节点
                if(head.left != null){
                    curr.next = head.left;
                    curr = curr.next;
                }
                // 尝试链接右节点
                if(head.right != null){
                    curr.next = head.right;
                    curr = curr.next;
                }
                head = head.next;
            }
            // 将head移动到当前这层的的第一个，准备链接下一层
            head = tmp.next;
        }
    }
}

Bingo

2017-08-13 09:59:11 3楼#1层

C++解法：

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode *leftMost = root;
        while (leftMost) {
            TreeLinkNode *p = leftMost;
            while (p && !p->left && !p->right) p = p->next;
            if (!p) return;
            leftMost = p->left ? p->left : p->right;
            TreeLinkNode *cur = leftMost;
            while (p) {
                if (cur == p->left) {
                    if (p->right) {
                        cur->next = p->right;
                        cur = cur->next;
                    }
                    p = p->next;
                }
                else if (cur == p->right) {
                    p = p->next;
                } else {
                    if (!p->left && !p->right) {
                        p = p->next;
                        continue;
                    }
                    cur->next = p->left ? p->left : p->right;
                    cur = cur->next;
                }
            }
        }
    }
};

取消

回复

推荐圈子

LeetCode交流圈