题目:
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
题意:
伴随着问题《Populating Next Right Pointers in Each Node》
假设给定的这颗树是随意类型的树。你之前的解法是否依旧可行呢?
注意:
你仅仅能使用常数空间。
比方
给定例如以下的二叉树
1
/
2 3
/
4 5 7
调用你的函数之后,这颗二叉树应该是例如以下的样子:
1 -> NULL
/
2 -> 3 -> NULL
/
4-> 5 -> 7 -> NULL
算法分析:
* 总体思想与《Populating Next Right Pointers in Each Node》相同。相同是递归
* 可是在相邻节点为空的情况下,须要去寻找不为空的第一个节点。并与之相连
AC代码:
<span style="font-family:Microsoft YaHei;font-size:12px;">public class Solution { public void connect(TreeLinkNode root) { if (root == null) return; //假设右孩子不为空。左孩子的next是右孩子。//反之,找root next的至少有一个孩子不为空的节点 if (root.left != null) { if (root.right != null) { root.left.next = root.right; } else { TreeLinkNode p = root.next; while (p != null && p.left == null && p.right == null) p = p.next; if (p != null) root.left.next = p.left == null ? p.right : p.left; } } //右孩子的next 根节点至少有一个孩子不为空的next if (root.right != null) { TreeLinkNode p = root.next; while (p != null && p.left == null && p.right == null) p = p.next; if (p != null) root.right.next = p.left == null ?
p.right : p.left; } connect(root.right); connect(root.left); } }</span>