首页 > 代码库 > Populating Next Right Pointers in Each Node II

Populating Next Right Pointers in Each Node II

2024-07-17 17:45:57   224人阅读

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

思路：自顶向下链接二叉树的每一层，当处理到第i层时，第i-1层的所有节点已经构成一个单向链表。依次遍历第i-1层便可顺利完成对第i层的链接。因为去掉了输入是完全二叉树的限定，因此内层循环比完全二叉树的会稍微复杂一些。

 1 class Solution { 2 public: 3     void connect( TreeLinkNode *root ) { 4         TreeLinkNode *head = root; 5         while( head ) { 6             TreeLinkNode *newHead = 0, *prevNode = 0; 7             while( head ) { 8                 if( head->left ) { 9                     if( !prevNode ) {10                         newHead = prevNode = head->left;11                     } else {12                         prevNode->next = head->left;13                         prevNode = prevNode->next;14                     }15                 }16                 if( head->right ) {17                     if( !prevNode ) {18                         newHead = prevNode = head->right;19                     } else {20                         prevNode->next = head->right;21                         prevNode = prevNode->next;22                     }23                 }24                 head = head->next;25             }26             head = newHead;27         }28         return;29     }30 };

 


联系
我们