本文主要是介绍LeetCode - 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 toNULL.
Initially, all next pointers are set toNULL.
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
题意:
填充每个next指针,指向它的下一个右节点。如果没有下一个右节点,则应该将下一个指针设置为toNULL。
最初,所有next指针都设置为toNULL。
注意:
您可以只使用常量的额外空间。
您可以假设它是一个完美的二叉树(即,所有叶节点都位于同一级别,并且每个父节点都有两个子节点)。
解题思路:
树的层序遍历,既然是树的遍历那就可以使用递归来解决。
递归的思路:
首先判断左结点是否存在,存在就把左结点的next指针赋给 右结点。这里并不需要判断右结点是否存在,因为这是个完全二叉树,左结点存在那么右结点也一定存在了。
其次判断右结点是否存在,判断右结点存在之后有两种情况,
第一种是上面那种 5 的情况,这时候需要将右结点的next指针跨域赋给其父节点的兄弟结点的左结点。
第二种是7的情况,那么需要将右结点赋null。
代码如下:
public void connect(TreeLinkNode root) {if(root == null) {return;}if(root.left != null) {root.left.next = root.right;}if(root.right !=null) {if(root.next == null) {root.right.next = null;}else {root.right.next = root.next.left;}}connect(root.left);connect(root.right);}
这篇关于LeetCode - populating-next-right-pointers-in-each-node的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!