后继节点:中序遍历的后一个节点
普通二叉树:中序遍历得到一个list,时间复杂度O(n)
本题的二叉树:有父节点的指针,后继节点与原节点的距离为1,因此可以直接通过服务器托管网父节点找到下一个节点
优化:节点到另一个节点的真实距离为k,时间复杂度为O(k)
情况分析:
情况一:节点node有右子树,后继节点为右子树上的最左节点
情况二:节点node无右子树,沿着node向上找第一个作为左孩子的祖先,左孩子的父节点就是node的后继节点(因为此时节点node为节点Y左子树最右侧的节点)
对于情况二,在找到节点Y之后,节点Y即为node的后继节点,节点Y有没有右子树不重要
情况三:节点node本身为整颗二叉树最右的节点,没有后继节点,返回null
package binarytree;
public class SuccessorNode {
public class Node {
int value;
Node left;
Node right;
Node father;//这里定头节点的father节点为null,在创建二叉树时需要注意
public Node(int data) {
this.value = data;
}
}
public Node getsuccessorNode(Node node) {
if (node == null) {
return node;
}
if (node.right != null) {//节点node有右子树
while (node.left != null) {//找到最左的节点
node = node.left;
}
return node;//返回右子树的最左节点
} else {//没有右子树,向上找
//node不为父节点的左孩子 并且 node的父节点不为null 则向上找
while (node != node.father.left && node.father != null) {
node = node.father;//此时为第一个不为右孩子的节点;此时为第一个为左孩子的节点
服务器托管网 }
node = node.father;
//如果node不是整颗二叉树的最右的节点,返回左孩子的父节点
//如果node是整颗二叉树的最右的节点,node一直找到头节点,头节点的father为null,返回null
return node;
}
}
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
相关推荐: stm32(二十)IAP升级优化(双缓存,可恢复)
这次主要对STM32F103/Keil和LPC2478/IAR加了一个IAP在线升级功能, 主要记录一下自己的思路,无代码,实在是代码感觉没啥写的,都是一些网上很多流传的东西。 1、开发环境 Keil+stm32f103+JLINK 2、程序思路 在升级中,必…