Leetcode c++ Populating Next Right Pointers in Each Node - JavaYu

Leetcode c++ Populating Next Right Pointers in Each Node - JavaYu

eetcode笔记（15）Populating Next Right Pointers in Each Node

• June 2, 2014
• 1 条评论

Given a binary tree

C++

struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; }

1 2 3 4 5

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 Initially, all next pointers are set to 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). For example, Given the following perfect binary tree,

C++

1 / \ 2 3 / \ / \ 4 5 6 7

1 2 3 4 5

1        /  \       2    3      / \  / \     4  5  6  7

After calling your function, the tree should look like:

C++

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

1 2 3 4 5

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

这一题的Accept率很高，但是很有意思，绕了半天才写出来一个复杂的思路。 这题想到层序遍历，直接遍历的同时设置next很简单但是需要constant space。所以开始考虑其他的思路（其实层序遍历是可以的，参见 

Populating Next Right Pointers in Each Node II 的解法）。 先序后序中序在这题中的差别不大，因为不需要输出root节点，对于root也没有什么重要的操作。从图遍历的角度来看，他们都属于DFS，而层序属于BFS。这一题的问题就在于，怎么把BFS里直观的连接方式移植到DFS里来。 解决方案是：DFS的同时，设置好当前层所有节点的next，包括当前范围的最后一个节点v。在树中，v和v->next之前的距离可能很远，例如v…root…v->next，其中v是root->left子树 T1的最右节点，v->next 是root->right子树T2的最左节点。这里的难点就是，在T2尚未被traverse的情况下，怎么找到v->next。 解决方案是：利用parent的next。在DFS的同时，可以逐步确定每一层的节点的next，只要上一层节点p的next已知，p->right的next就应该是p->next->left。从这个意义上来讲，我们需要采用先序或者中序遍历，因为parent的next需要在parent->right之前设置好。 代码如下：

Read full article from Leetcode c++ Populating Next Right Pointers in Each Node - JavaYu