【算法专栏】二叉树的下一个节点
本系列是《剑指offer》或leetcode的JavaScript版本。 每期1-2个算法，也有可能是一个类别。 文章包括题目、思路以及代码。 如果您对本期有不同或者更好的见解，请后台留言，喜欢请点个好看，谢谢阅读。
题目
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路
中序遍历的顺序 左 - 根 - 右
所以寻找下一个节点的优先级应该反过来 优先级 右 - 根 - 左
- 右节点不为空 - 取右节点的最左侧节点
- 右节点为空 - 如果节点是父亲节的左节点 取父节点
- 右节点为空 - 如果节点是父亲节的右节点 父节点已经被遍历过，再往上层寻找...
- 左节点一定在当前节点之前被遍历过
以下图的二叉树来分析：
中序遍历：CBDAEF
- B - 右节点不为空，下一个节点为右节点D
- C - 右节点为空，C是父节点的左节点，取父节点B
- D - 右节点为空，D是父节点的右节点，再往上蹭分析，B是其父节点的左节点，取B的父节点A
- F - 右节点为空，F是父节点的右节点，没有符合条件的节点，F为遍历的最后一个节点，返回null
代码
/*function TreeLinkNode(x){
this.val = x;
this.left = null;
this.right = null;
this.next = null;
}*/
function GetNext(pNode) {
if (!pNode) {
return null;
}
if (pNode.right) {
pNode = pNode.right;
while (pNode.left) {
pNode = pNode.left;
}
return pNode;
} else {
while (pNode) {
if (!pNode.next) {
return null;
} else if (pNode == pNode.next.left) {
return pNode.next;
}
pNode = pNode.next;
}
return pNode;
}
}考察点
- 二叉树
- 复杂问题拆解
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-07-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录