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

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if(!pNode) return nullptr;
        if(pNode->right){
            TreeLinkNode* cur = pNode->right;
            while(cur->left){
                cur = cur->left;
            }
            return cur;
        }
        while(pNode){//别忘了首位处理，可能没有上一个，空指针没有元素不能访问。
            if(pNode->next&&pNode->next->left==pNode) return pNode->next;
            pNode = pNode->next;
        }
        return nullptr;
    }
};

其他方法：中序遍历下一位最简单就是直接找到根节点然后中序遍历一次，然后找到要求节点的下一位。

唯一需要注意的一点就是保存为指针，因为需要比较本质上是不是同一个，也就是地址，地址比较用指针比较。

本题方法：

我给出的方法是直接通过中序遍历的规律找，中序就是左中右。

这个中是指自己，从中序遍历的递归函数的写法就可以看出来，在左右递归中间写当前节点的处理代码。

所以它左边肯定已经搞完了，下一步要往右边走，如果有右子树那就是右子树里最左的部分。

如果没有右子树呢？那也要往右边走，但是它自己不会再作为根节点了，而是一个更大的树的左边部分（因为那个根不是这个节点，只能在上面，又不能是右边部分，因为作为右子树已经完蛋了必须依靠外界），所以一直往上找到自己是左子树的部分，返回那个大树的根节点。

为什么优先自己走呢？因为本节点必然是大树的左树，而左树整颗都在大树根节点的左边，往右走时会先走到此节点的右子树。