剑指Offer 8. 二叉树的下一个节点

题目

给定一棵二叉树和其中的一个结点,如何找出中序遍历顺序的下一个结点?树中的结点除了有两个分别指向左右子结点的指针以外,还有一个指向父结点的指针。

解答1[Java]:

主要分为两种情况:

①如果一个节点的右子树不为空,那么在中序遍历的下一个节点就是其【右子树的最左节点】。

②如果一个节点的右子树为空,那么在中序遍历的下一个节点就是其【最近的一个祖先节点,这个祖先节点的左子树包含该节点】。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if (pNode.right != null) {
TreeLinkNode node = pNode.right;
while (node.left != null)
node = node.left;
return node;
} else {
while (pNode.next != null) {
TreeLinkNode parent = pNode.next;
if (parent.left == pNode)
return parent;
pNode = pNode.next;
}
}
return null;
}
}

public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null; // next指向双亲结点

TreeLinkNode(int val) {
this.val = val;
}
}