如果希望按照非递减顺序访问二叉树所有节点,二叉树中至少包含一个节点

　　055-79007、二叉树的下一个节点【C详解】_ blog _ Sword指的是重建二叉树的报价

　　给定二叉树的一个节点，请找出中序遍历序列中的下一个节点。

　　注意：

　　如果给定节点是中间顺序遍历序列中的最后一个，则返回一个空节点；二叉树不能为空，给定节点不能为空；样品

　　假设二叉树为：[2 [2，1，3，null，null，null，null]]，给出值等于2的节点。

　　应该返回返回值等于3的节点。

　　说明：这个二叉树的结构如下。2的后继节点是3。

　　2

　　/\

　　3个想法(模拟)

　　这个主题是在二叉树中寻找一个给定节点的后继节点。

　　刚才讨论的情况，如下图所示：

　　如果当前节点有一个右子节点，则右子树中最左边的节点是当前节点的后继节点。比如F的后继者是H；

　　如果当前节点没有右子，就需要一路向上搜索父域，找到第一个父是左子的节点，这个节点的父就是当前节点的后继。举个例子，如果当前节点是D，那么第一个满足是其父左子的节点是F，那么C的父就是D的后继，也就是F是D的后继。

　　时间复杂性分析

　　无论向上看还是向下看，遍历的节点总数都不大于树的高度。所以时间复杂度是，其中h是树的高度。

　　代码/* *

　　*二叉树节点的定义。

　　*结构树节点{

　　* int val

　　* TreeNode * left

　　* TreeNode * right

　　* TreeNode * father

　　* TreeNode(int x) : val(x)，left(NULL)，right(NULL)，father(NULL) {}

　　* };

　　*/

　　类别解决方案{

　　公共：

　　TreeNode * in order successor(TreeNode * p){

　　If (p- right) {//如果当前节点有右子树，则搜索右子树，直到找到右子树最左边的节点。

　　p=p-右；

　　而(p-left)p=p-left；

　　返回p；

　　}

　　//如果P有父节点，P是P的父节点的右子，继续查找。

　　而(p-父p==p-父-右)p=p-父；

　　返回p-父亲；//最后一个拐点的父节点是后继节点。

　　}

　　};

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。