抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

二叉树的下一个结点

题目:给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

此二叉树的中序遍历为:D、B、H、E、I、A、F、C、G

解题思路:利用二叉树的中序遍历特性进行分析,用具体的二叉树做例子。规则如下:

情况一:节点为空,则直接为空。

情况二:当右节点不为空,则一直找到右节点的左子节点。

情况三:右节点为空,若该节点是其父节点的左孩子,则返回父节点;否则按此规则继续向上遍历其父节点的父节点。
循环直到满足条件:该节点是其父节点的左孩子

Code:牛客已测试通过

TreeLinkNode getNext(TreeLinkNode pNode) {
//情况一:节点为空 则直接为空
if (pNode == null) {
return null;
}
TreeLinkNode pNext = null;
if (pNode.right != null) {
//情况二:当右节点不为空 则一直找到右节点的左子节点
TreeLinkNode pRight = pNode.right;
while (pRight.left != null) {
pRight = pRight.left;
}
pNext = pRight;
} else if (pNode.parent != null) {
//情况三:右节点为空,若该节点是其父节点的左孩子,则返回父节点;否则按此规则继续向上遍历其父节点的父节点
// 循环直到满足条件:该节点是其父节点的左孩子
TreeLinkNode pCurrent = pNode;
TreeLinkNode pParent = pNode.parent;
while (pParent != null && pCurrent == pParent.right) {
pCurrent = pParent;
pParent = pParent.parent;
}
//满足条件 跳出循环 此父节点为我们要找的父节点
pNext = pParent;
}
return pNext;
}

class TreeLinkNode {
int mValue;
TreeLinkNode left;
TreeLinkNode right;
TreeLinkNode parent;
}

这题主要是理解中序遍历,然后思路理清,找到规律即可。


0条评论

发表评论