为二叉树添加下一个兄弟节点的指针（完全二叉树）

妖狐艹你老母 2022-10-01 13:55 150阅读 0赞

[为什么80%的码农都做不了架构师？>>> ][80_] ![hot3.png][]

# Populating Next Right Pointers in Each Node #

问题：

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`.

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,

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

解决：

① 本题是树的层序遍历的应用。BFS，由于是完全二叉树，所以若节点的左子结点存在的话，其右子节点必定存在，所以左子结点的next指针可以直接指向其右子节点，对于其右子节点的处理方法是，判断其父节点的next是否为空，若不为空，则指向其next指针指向的节点的左子结点，若为空则指向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 \{ //0ms  
public void connect(TreeLinkNode root) \{  
if(root == null) return;  
if(root.left != null) \{  
root.left.next = root.right;  
\}  
if (root.right != null) \{  
root.right.next = root.next == null ? null : root.next.left;  
\}  
connect(root.left);  
connect(root.right);  
\}  
\}

② 非递归解法，使用queue，由于是层序遍历，每层的节点都按顺序加入queue中，而每当从queue中取出一个元素时，将其next指针指向queue中下一个节点即可。

public class Solution \{ //4ms  
public void connect(TreeLinkNode root) \{  
if(root == null) return;  
Queue<TreeLinkNode> queue = new LinkedList<>();  
queue.offer(root);  
while(! queue.isEmpty())\{  
int count = queue.size();  
for (int i = 0;i < count ;i ++ ) \{  
TreeLinkNode cur = queue.poll();  
if(i < count - 1)\{  
cur.next = queue.peek();  
\}  
if(cur.left != null) queue.offer(cur.left);  
if(cur.right != null) queue.offer(cur.right);  
\}  
\}  
\}  
\}

③ 使用4个指针，空间复杂度O（1）。

![20161004_sRHs.jpg][]

class Solution\{ //1ms  
public void connect(TreeLinkNode root) \{  
if(root == null) return;  
TreeLinkNode lastHead = root;//前一层的头节点  
TreeLinkNode lastCurrent = null;//前一层的指针  
TreeLinkNode currentHead = null;//当前层的头节点  
TreeLinkNode current = null;//当前层的指针  
while(lastHead != null)\{  
lastCurrent = lastHead;  
while(lastCurrent != null)\{  
if(currentHead == null)\{  
currentHead = lastCurrent.left;  
current = lastCurrent.left;  
\}else\{  
current.next = lastCurrent.left;  
current = current.next;  
\}  
if(currentHead != null)\{  
current.next = lastCurrent.right;  
current = current.next;  
\}  
lastCurrent = lastCurrent.next;  
\}  
//更新头节点  
lastHead = currentHead;  
currentHead = null;  
\}  
\}  
\}

转载于:https://my.oschina.net/liyurong/blog/1540050

[80_]: https://my.oschina.net/u/2663968/blog/3051541
[hot3.png]: /images/20220118/d97af7db0f00443cb12817db84a840a6.png
[20161004_sRHs.jpg]: https://static.oschina.net/uploads/img/201709/20161004_sRHs.jpg