关注
【题目】
现在有一种新的二叉树节点类型如下:
public class Node {
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int data) {
this.value = data;
}
}
该结构比普通二叉树节点结构多了一条指向父节点的parent指针。假设有一棵Node类型的节点组成的二叉树,树中每个节点的parent指针都正确的指向自己的父节点,头节点的parent指向null。只给一个在二叉树中的某个节点node,请实现返回node的后继节点的函数。在二叉树的中序遍历的序列中,node的下一个节点叫做node的后继节点。
例如,下图的二叉树:
__________6__________
/ \
___3___ ___9___
/ \ / \
1__ 4__ __8 10
\ \ /
2 5 7
中序遍历的结果为:1,2,3,4,5,6,7,8,9,10
所以节点1的后继为节点2,节点2的后继为节点3,…,节点10的后继为null
public Node getNextNode(Node node) {
if (node == null) {
return node;
}
if (node.right != null) {
return getLeftMost(node.right);
} else {
Node parent = node.parent;
while (parent != null && parent.left != node) {
node = parent;
parent = node.parent;
}
return parent;
}
}
public Node getLeftMost(Node node) {
if (node == null) {
return node;
}
while (node.left != null) {
node = node.left;
}
return node;
}
查看原帖
点赞 6
相关推荐
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
382513次浏览 7622人参与
# 应届生初入职场,求建议 #
21971次浏览 537人参与
# 晒一晒我的offer #
2800625次浏览 49738人参与
# 在国企工作的人,躺平了吗? #
71623次浏览 868人参与
# 简历中的项目经历要怎么写 #
378312次浏览 6360人参与
# 非技术岗薪资爆料 #
6918次浏览 135人参与
# 你更愿意参加线上面试还是线下面试? #
6472次浏览 90人参与
# 非技术薪资爆料 #
63719次浏览 954人参与
# 华为求职进展汇总 #
438851次浏览 4411人参与
# 第一次面试 #
15704次浏览 240人参与
# 租房前辈的忠告 #
20765次浏览 1648人参与
# 应届生应该先就业还是先择业 #
12105次浏览 114人参与
# 安利/避雷我的岗位 #
122307次浏览 2752人参与
# 来聊聊机械薪资天花板是哪家 #
20796次浏览 165人参与
# 机械人怎么评价今年的华为 #
53998次浏览 442人参与
# 谈薪时HR压价该怎么应对 #
33034次浏览 204人参与
# 通信硬件薪资爆料 #
145093次浏览 1078人参与
# 毕业租房也有小确幸 #
19818次浏览 1250人参与
# 数据人offer决赛圈怎么选 #
36619次浏览 658人参与
# 正在实习的你,有转正机会吗? #
83256次浏览 865人参与