题解 | #二叉树的下一个结点#

算法：模拟

中序遍历的顺序是左根右；
分类讨论：
1、如果遍历到了当前结点，当前点如果有右儿子，那它的后继是右子树中最左边的一个；
左中右：如果当前结点有右子树（想象成 中结点），那么他的后继结点在右边，右子树的最左边；

2、当前结点没有右子树，那么要沿着它的父结点往上找，找到第一个是其父结点的左儿子的结点，该结点的父结点就是当前结点的后继。
左中右：如果当前结点没有右子树（想象成 该结点在某结点Node的左子树），那么找到他的后继结点Node

• 首先向上找父节点pNode
• 直到某个pNode为mNode的左子节点时
• mNode即为Node；

时间复杂度:O(h)
不论往上找还是往下找，总共遍历的结点数都不大于树的高度。所以时间复杂度是 O(h)，其中 h 是树的高度。

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

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
//       中序遍历的顺序是左根右；
// 分类讨论：
// 1、如果遍历到了当前结点，当前点如果有右儿子，那它的后继是右子树中最左边的一个；
        if(pNode.right!=null){
            return Getlast_leftNode(pNode.right);
        }else{
// 2、当前结点没有右子树，那么要沿着它的父结点往上找，找到第一个是其父结点的左儿子的结点，该结点的父结点就是当前结点的后继。
            return GetFather_IFLeftNode(pNode);
        }

     public TreeLinkNode Getlast_leftNode(TreeLinkNode Node){
// 左中右：如果当前结点有右子树（想象成 中结点），那么他的后继结点在右边，右子树的最左边；
         if(Node.left!=null){
             return Getlast_leftNode(Node.left);
         }
         return Node;
     }

    public TreeLinkNode GetFather_IFLeftNode(TreeLinkNode Node){
// 左中右：如果当前结点没有右子树（想象成 **该结点在某结点Node的左子树**），那么找到他的后继结点Node
// - 首先向上找父节点pNode
// - 直到某个pNode为mNode的左子节点时(此时mNode = pNode.Next)
// - mNode即为Node；
        if(Node.next != null){
            if(Node.next.left == Node){
                return Node.next;
            }else{
                return GetFather_IFLeftNode(Node.next);
            }
        }
        return null;
     }
}