【二叉树】剑指offer 8 二叉树的下一个结点
描述
给定一个二叉树其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示,从子节点指向父节点的用虚线表示
题解
这题需要对各种情况分类讨论,一共有三种情况
- 第一种:如果这个节点的右孩子不为空,根据中序遍历的特点,它的下一个节点是它的右孩子的最左边的孩子
- 第二种:如果这个节点是其父亲的左孩子,根据中序遍历的特点,它的下一个节点就是其父亲(注意如果父亲为
null
,则该节点是根节点,此时返回null
)
- 第三种:最复杂的一个情况,该节点为其父亲的右孩子,此时需要向上找到一个祖先节点
A
,A
是其父亲的左孩子(即回到了第二种情况),这个情况可以通过画图分析得出,例如下图中的节点4,它的下一个节点为3的父节点5,因为3是其父节点5的左孩子
所有代码
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode) {
// 1. 右孩子不空,则找到它右孩子的最左孩子
if (pNode.right != null) {
pNode = pNode.right;
// 找到最左的节点
while (pNode.left != null)
pNode = pNode.left;
return pNode;
}
TreeLinkNode parent = pNode.next;
if (parent == null)
return null;
// 2. 右孩子为空,且是父亲的左孩子,父节点为下一节点
if (parent.left == pNode)
return pNode.next;
// 3. 右孩子为空,且是父亲的右孩子
while (parent != null) {
// 向上找父亲,直到节点是其父亲的左孩子,即第二种情况
if (parent.left == pNode)
return parent;
pNode = parent;
parent = parent.next;
}
return null;
}
public static void main(String[] args) {
TreeLinkNode r = new TreeLinkNode(1);
r.left = new TreeLinkNode(2);
r.left.next = r;
TreeLinkNode pnow = r.left;
pnow.right = new TreeLinkNode(3);
pnow.right.next = pnow;
pnow = pnow.right;
pnow.right = new TreeLinkNode(4);
pnow.right.next = pnow;
TreeLinkNode res = new Solution().GetNext(pnow.right);
System.out.println(res.val);
}
}
- 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
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48