题目描述
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
解题思路
中序遍历规则--》左根右。
所以存在两大类情况:
-
右子树存在,下一结点就是右子树最左下结点;
-
右子树不存在,也有两类:
-
是父结点的左孩子,下一结点就是父结点;
-
是父节点的右孩子,递归找父节点,直到所在树是其父结点的左子树,下一结点就是此结点。
-
代码
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if (pNode == null)
return null;
if (pNode.right != null) {
pNode = pNode.right;
while (pNode.left != null)
pNode = pNode.left;
return pNode;
} else {
while (pNode.next != null && pNode.next.left != pNode)
pNode = pNode.next;
return pNode.next;
}
}
}
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于