剑指Offer57 二叉树的下一个节点

Java 题解

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

情形 1

如果一个节点有右子树，那么他的下一个节点就是他的右子树的最左子节点（从右子节点出发一直沿着指向左子节点的指针就能找到他的下一个子节点），如：a的下一个节点就是d。

情形 2

如果一个节点没有右子树，且此节点是他的父节点的左子节点，他的下一个节点就是他的父节点，如：节点d的下一个节点是b。

情形 3

如果一个节点既没有右子树，且此节点又是父节点的右子节点。我们可以沿着此节点指向父节点的指针一直向上遍历，直到找到一个是他父节点的左子节点的节点，如：i节点的下一个节点，沿着他的父节点的指针遍历，先到达e，但是e是他父节点b的右子节点，所以继续向上，到达b节点，b是他父节点a的左子节点，所以i的下一个节点是a。

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null)
            return null;

        TreeLinkNode pNext = null;

        // 情形 1
        // 如果一个节点有右子树，那么他的下一个节点就是他的右子树的最左子节点
        // （从右子节点出发一直沿着指向左子节点的指针就能找到他的下一个子节点）
        if(pNode.right != null){
            TreeLinkNode pRight = pNode.right;
            while(pRight.left!=null){
                pRight = pRight.left;
            }
            pNext = pRight;
        }else if(pNode.next != null){
            // 情形 2
            // 如果一个节点没有右子树，且此节点是他的父节点的左子节点，他的下一个节点就是他的父节点
            if(pNode.next.left == pNode){
                pNext = pNode.next;
            }

            // 情形3
            // 如果一个节点既没有右子树，且此节点又是父节点的右子节点。
            // 我们可以沿着此节点指向父节点的指针一直向上遍历，直到找到一个是他父节点的左子节点的节点，
            else {
                TreeLinkNode curr = pNode;
                TreeLinkNode pParent = pNode.next;
                while(pParent!=null && curr == pParent.right){
                    curr = pParent;
                    pParent = pParent.next;
                }
                pNext = pParent;
            }

        }
        return pNext;
    }
}