二叉树结点中序遍历的前驱和后继

二叉树的中序遍历结构是：左-根-右，其中左和右也是如此。所以某个结点的前驱结点是左子树的最右结点，后继节点是右子树的最左节点

但如果是这种情况：左-根或根-右，那就需要考虑当前子树在父节点中的结构了

       1
  2          3
4   5      6   7
      8  9 
复制代码

比如9的前驱节点是1，属于根-(根-右)这种情况。8的后继节点是1，属于(左-根)-根的情况

这两种情况下面分别讨论下，先定义树节点

class Node{
    int val;
    Node parent;
    Node left;
    Node right;
}
复制代码

前驱结点

思路

• 如果node有左子树，则找到左子树的最右结点
• 如果node没有左子树，则找到父结点路径上的向左的拐点，相当于找后继节点的逆过程

class Solution{
    public Node inorderSuccessor(Node node){
        if(node==null){
            return null;
        }
        
        if(node.left!=null){
            node=node.left;
            while(node.right!=null){
                node=node.right;
            }
            return node;
        }
        
        while(node.parent!=null&&node!=node.parent.right){
            node=node.parent;
        }
        return node.parent;
    }
}
复制代码

后继节点

思路

• 如果node有右子树，则找到右子树的最左结点
• 如果node没有右子树，则找到父结点路径上的向右的拐点，相当于找前驱节点的逆过程

class Solution{
    public Node inorderSuccessor(Node node){
        if(node==null){
            return null;
        }
        
        if(node.right!=null){
            node=node.right;
            while(node.left!=null){
                node=node.left;
            }
            return node;
        }
        
        while(node.parent!=null&&node!=node.parent.left){
            node=node.parent;
        }
        return node.parent;
    }
}
复制代码