脚本宝典收集整理的这篇文章主要介绍了【刷算法】二叉树中序遍历的下一个结点,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
题目描述
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
分析
对于二叉树中序遍历来说,某node的下一个节点可以分为以下几种情况:
- node.right 不为 null时,根据中序遍历的定义,下一个节点则是node右子树里最左边的节点。
- node.right 为 null时,考察node是否为node.parent的左节点,如果是的话,node的下一个节点就是node.parent;否则,考察node.parent是否为node.parent.parent的左节点,依次这样向上探索下去。
代码实现
/*function TreeLinkNode(x){
this.val = x;
this.left = null;
this.right = null;
this.next = null;
}*/
function GetNext(node)
{
if(node === null)
return null;
if(node.right !== null){
node = node.right;
while(node.left !== null){
node = node.left;
}
return node;
}else{
while(node.next !== null){
if(node === node.next.left)
return node.next;
node = node.next;
}
}
return null;
}
以上是脚本宝典为你收集整理的【刷算法】二叉树中序遍历的下一个结点全部内容,希望文章能够帮你解决【刷算法】二叉树中序遍历的下一个结点所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。