二叉树的下一个结点

树的结构

public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

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

注意父节点是通过每个节点的next指针定位的。

由于是求中序遍历的下一节点，中序遍历的模式是左、根、右，因此我们只要判断一个节点是否有右节点，如果有，则中序遍历的下一个节点就是其右子树的最左的叶子节点；如果没有，则中序遍历的下一个节点就是判断当前节点是否是父节点的左节点，如果是，则返回父节点；如果不是，则继续判断父节点是否是它的直接父节点的左节点，依次类推，直到找到一个是父节点的左节点的节点，返回其父节点，或者找到整个树的根节点为止。

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode p) {
        if (p == null)
            return null;
        if (p.right != null) {
            // 右子树非空，找右子树的最左节点
            TreeLinkNode r = p.right;
            while (r.left != null) {
                r = r.left;
            }
            return r;
        } else {
            // 右子树为空，则向上找直到第一个作为左节点祖先的父节点，或到整个树的根停止
            while (p.next != null) {
                TreeLinkNode parent = p.next;
                if (p == parent.left) {
                    return parent;
                }
                p = p.next;
            }
            return null;
        }
    }
}