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

Populating Next Right Pointers in Each Node II leetcode java

2024-07-15 15:15:04   221人阅读

题目：

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的区别就是binary tree不是完全二叉树。
 所以root.right.next就不一定等于root.next.left。
 所以，目标就是先确定好root的右孩子的第一个有效next连接点，然后再处理左孩子。

代码如下：
 1     public void connect(TreeLinkNode root) {  
 2         if (root == null) 
 3             return;  
 4   
 5         TreeLinkNode p = root.next;  
 6         /*
 7         因此，这道题目首要是找到右孩子的第一个有效的next链接节点，然后再处理左孩子。然后依次递归处理右孩子，左孩子
 8         */
 9         while (p != null) {  
10             if (p.left != null) {  
11                 p = p.left;  
12                 break;  
13             }  
14             if (p.right != null) {  
15                 p = p.right;  
16                 break;  
17             }  
18             p = p.next;  
19         }  
20   
21         if (root.right != null) {  
22             root.right.next = p;  
23         }  
24   
25         if (root.left != null) {
26             if(root.right!=null)
27                 root.left.next = root.right;
28             else
29                 root.left.next = p;
30         }  
31   
32         connect(root.right);
33         connect(root.left);
34     } 


联系
我们