@TOC

剑指offer 08 二叉树的下一个节点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回 。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null; // 指向父结点的指针

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

解题思路：根据中序遍历的特点思考

假设二叉树如下图所示：

1. 该结点有右孩子，则下一个结点是其右孩子的左子树中最左的结点（如2节点，下一个节点是3节点）
2. 该结点没有右孩子
   • 该节点是父节点的左孩子，则下一结点就是其父节点（如1节点，下一个节点是2节点）
   • 该结点是父节点的右孩子，则一直往上找父节点，直到该父节点是该父节点的父节点的左孩子,则下一节点便是该父节点的父节点（如3节点，下一个节点是4），不存在这样的父结点，则没有下一个结点（如9节点）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode father;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode p) {
        if(p==null) return null;

        if(p.right!=null){//该节点有右孩子
            p = p.right;
            while(p.left!=null){
                p = p.left;
            }
           return p;
        }  
         //该节点是父节点的左孩子
        if(p.father!=null && p.father.left == p) {
            return p.father;
        }  
       //该节点是父节点的右孩子
        while(p.father!=null && p.father.right == p){
            p = p.father;
        }
        return p.father;
    }
}