【剑指Offer】二叉树的下一个结点

Posted on | In ,

题目

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

实现

1
2
3
4
5
6
7
8
9
10
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public TreeLinkNode GetNext(TreeLinkNode pNode) {
    if (pNode == null)
        return null;

    if (pNode.right != null) {
        pNode = pNode.right;

        while (pNode.left != null)
            pNode = pNode.left;
    }
    else {
        while (pNode.next != null && pNode.next.right == pNode)
            pNode = pNode.next;

        pNode = pNode.next;
    }

    return pNode;
}