在二叉树中找到一个节点的后续节点

根据题意可知，后续节点就是指，中序遍历的后一节点，所以最容易的方式就是直接求的根节点，然后求出中序遍历结果保存起来进行查找。但是时间空间复杂度都比较大。

想一下，我们可以分情况来讨论有哪些情况

• 如果当前节点有右子树，那么它的下一节点是右子树的最左节点
• 如果没有右子树，并且他是父节点的左子节点，那么他的下一节点就是父节点
• 如果没有右子树，并且他是父节点的右子节点。就向上寻找node的后续节点，假设向上移动到的节点为s，s的父节点为p，如果发现s是p的左子节点，那么p就是node的后续节点
• 如果上一步找到空节点，则说明没有后续节点

代码如下

剑指上也有这个题，我直接贴我在剑指上写的代码了

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

    TreeLinkNode(int val) {
        this.val = val;
    }
}
public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) return pNode;
        
        if (pNode.right != null) {
            return getLeft(pNode.right);
        }
        
        TreeLinkNode p = pNode.next;

        while (p != null && p.left != pNode) {
            pNode = p;
            p = p.next;
        }
        return p;
  

    }

    public TreeLinkNode getLeft(TreeLinkNode node) {
        if (node == null) return null;
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }