LeetCode每日一题 之 二叉树的下一个结点

题目

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

我感觉可以自己先做做，你说呢！！！！！！

解题思路

先看一个颗二叉树

中序遍历的顺序是左中右，这颗树的中序遍历是ACBDFHEMG

观察可得到，所给结点如果

• 有右子树，那么他的下一个节点就是先找右子树，再向下一直找左子树。例如C结点，他的下一个点是B，也就是先找右子树D，再一直找左子树，找到B。
• 没有右子树，那么就需要往父节点方向找，怎么找，可以先想想看。。。。。。 答案：找到一个所在枝干是左子树为之

举个栗子🌰

没有右子树可能不好理解，我们看下上面的树。D和G都没有右子树，D的下一个节点是F，而G没有下一个结点。可以看出一直往父节点寻找，找到一个所在枝干是左子树为之。例如B没有右子树，向上找，找到D，在D的左子树上，命中，下一个就是D。G没有右子树，向上找，找到E，在右子树，继续找，找到F，还在右子树，无法向上了，说明不存在下一个结点。D没有右子树，向上找，找到C，在右子树，继续找，找到F，在左子树，命中，返回F。

代码

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode.right != null){
            //有右子树，先右，再一直左
            pNode = pNode.right;
            while(pNode.left != null){
                pNode = pNode.left;
            }
            return pNode;
        } else {
            //没有右子树，向上找树枝所在左侧的结点
            while(pNode.next != null){
                if(pNode.next.left == pNode){return pNode.next;}
                pNode = pNode.next;
            }
        }
        return null;
    }
}