>

自由软件精神——“自由、开放、分享”。自由软件自诞生之日起,就秉承了学术自由的思想,信奉科学无国界,知识应该全人类共享。

ubuntu精神——人道待人,天下共享连接人人的信念。具有 ubuntu 精神的人心胸开阔,乐于助人,见贤思齐而不忌妒贤能......

leetcode刷题 Populating Next Right Pointers

 

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

 

/**
 * 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) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (root == null) {
            return;
        }

        TreeLinkNode 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;
        }

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

        connect(root.right);
        connect(root.left);
    }
}

Meta

发布: 十二月 4, 2014

作者: Bone Lee 李智华

评论:  

字数统计: 246

下一篇: python heap

上一篇: leetcode刷题 Interleaving String

Bookmark and Share

Tags

leetcode test

comments powered by Disqus

返回顶部