《剑指offer第二版》面试题8:二叉树的下一个节点（java）

题目描述

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

解题思路:

1. 以如下二叉树为例，中序遍历为{d,b,h,e,i,a,f,c,g}，给定的二叉树节点用A表示。

         a
        /   \
       b     c
      / \   / \
     d  e  f  g
       / \
      h   i

2. 如果A有右子树，那它的下一个节点是右子树里最左节点。
3. 如果A没有没有右子树，并且A是A的父节点的左节点，那它的下一个节点就是他的父节点。
4. 如果A没有没有右子树，并且A是A的父节点的右节点，则沿着父节点的指针向上遍历，直到当前节点不是其父节点的右节点。则当前节点的父节点即为A的下一个节点。

代码

static class TreeNode1{
    String value;
    TreeNode1 left;
    TreeNode1 right;
    TreeNode1 parent;

    TreeNode1(String val){
        this.value = val;
    }
    @Override
    public String toString() {
        return value;
    }
}

TreeNode1 getInOrderNext(TreeNode1 curNode){
    if (curNode == null) {
        return null;
    }

    if (curNode.right != null) {
        // 存在右子树，那它的下一个节点是右子树里最左节点。
        TreeNode1 tmp = curNode.right;
        while (tmp.left != null) {
            tmp = tmp.left;
        }
        return tmp;
    }
    if (curNode.parent != null) {
        if (curNode == curNode.parent.left) {
            // 如果curNode没有没有右子树，并且curNode是curNode的父节点的左节点，那它的下一个节点就是他的父节点。
            return curNode.parent;
        }
        TreeNode1 tmp = curNode;
        // 如果curNode没有没有右子树，并且curNode是curNode的父节点的右节点，则沿着父节点的指针向上遍历，直到tmp节点不是其父节点的右节点。
        // 则tmp节点的父节点即为curNode的下一个节点。
        while (tmp.parent != null && tmp.parent.right == tmp) {
            tmp = tmp.parent;
        }
        return tmp.parent;
    }
    return null;
}