摘要：题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。分析对于二叉树中序遍历来说，某的下一个节点可以分为以下几种情况不为时，根据中序遍历的定义，下一个节点则是右子树里最左边的节点。
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
分析对于二叉树中序遍历来说，某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;
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/96154.html
摘要：重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。所以先通过前序遍历找出根节点，然后将中序遍历分为左右子树两组，最后对于每个子树依次递归调用。 重建二叉树 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}...
文章目录 一、题目1、题目描述2、基础框架3、原题链接 二、解题报告1、思路分析2、时间复杂度3、代码详解 三、本题小知识四、加群须知 一、题目 1、题目描述 给你一棵二叉搜索树，请按 中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。 样例输入： [5,3,6,2,4,null,8,1,null,null,nu...
摘要：因此，根据题目给出的先序遍历和中序遍历，可以画出二叉树选参考数据结构与算法描述实现二叉树算法浅谈数据结构二叉树慕课网实现二叉树算法前端树控件腾讯软件开发面试题 内容衔接上一章 数据结构与算法:常见排序算法 内容提要 什么是树 - 为什么使用树 二叉树 二叉查找树 红黑树 Ｂ、Ｂ＋树 堆 伸展树 树 可以点击链接感受下笔者用d3.js画的tree https://codepen...
摘要：同样结点树的二叉树，完全二叉树的深度最小。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。 二叉树的概念 二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 showImg(https://seg...
阅读 1458·2021-09-26 09:46
阅读 2491·2021-09-07 09:59
阅读 2574·2021-09-07 09:59
阅读 1713·2019-08-30 14:20
阅读 783·2019-08-26 13:39
阅读 3030·2019-08-26 12:24
阅读 677·2019-08-26 11:55
阅读 1111·2019-08-23 16:49
