Populating Next Right Pointers in Each Node--为每一个节点填充next right指针

原题:

Given a binary tree

=>给定一个二叉树

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *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.

=>把每一个节点的next指针指向它右面的节点,假如右边没有节点,则指向null

Initially, all next pointers are set to NULL.

=>所有的next节点都是初始化为null的。

Note:

=>注意

  • You may only use constant extra space.
  • =>最好只使用有限的额外空间
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
  • =>假设是一个完美的二叉树(就是所有的叶子都是在一个level上,所有的父子树都有两个子节点)

For example,

=>例如
 Given the following perfect binary tree,

=>给定的完美二叉树

         1
       /        2    3
     / \  /     4  5  6  7

After calling your function, the tree should look like:

=>在执行了函数之后,就如下图所示:

         1 -> NULL
       /        2 -> 3 -> NULL
     / \  /     4->5->6->7 -> NULL
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:

    void connect(TreeLinkNode *root) {
    }
};




晓东分析:

      首先想到的就是二叉树的遍历,只要把先遍历到的左子树指向右子树,然后就可以组成如下的三角形,其中null是初始化的值。(5也是指向null的,未画出)

            1  -> null
       /        \
      2  ->    3 ->null
     / \         / \
   4->5     6->7->null

下面一步,就是把5和6之间联系起来,这就是右子树的next指向自己next的左子树。这样就可以得到

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

下面就是各种遍历的算法选择了。选择了一个先序遍历,见http://blog.csdn.net/u011960402/article/details/14517135里面有详细描述。于是有了下面的代码


代码实现:

实现一:递归

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:

    void connect(TreeLinkNode *root) {
        if (NULL == root) {
            return;
        }

        TreeLinkNode *left = root->left;
        TreeLinkNode *right = root->right;

        /* set the next pointer for his left child */
        if (NULL != left) {
            left->next = right;
        }

        /* set the next pointer for his right child */
        if (NULL != right && NULL != root->next) {
            right->next = root->next->left;
        }

        /* do it recursively */
        connect(left);
        connect(right);

    }
};


运行结果:

14 / 14 test cases passed.
Status:

Accepted

Runtime: 52 ms


实现二:

非递归实现:

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root == NULL) return;
        stack<TreeLinkNode*> TreeStack;

        while(root || !TreeStack.empty()){
            while(root){
                TreeStack.push(root);
                if(root->left){
                    root->left->next = root->right;
                    if(root->next)
                        root->right->next = root->next->left;
                }
                root = root->left;
            }
            root = TreeStack.top();
            TreeStack.pop();
            root = root->right;
        }

    }
};

运行结果:

14 / 14 test cases passed.
Status:

Accepted

Runtime: 104 ms


令人奇怪的是非递归反而比递归的算法慢了,比较奇怪。


若您有更好的算法可以提出,谢谢




Populating Next Right Pointers in Each Node--为每一个节点填充next right指针

上一篇:Populating Next Right Pointers in Each Node


下一篇:Delphi 判断操作系统是32位或是64位