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

第二十二题 看懂了版本

通过点来判断的优化算法

/*
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==NULL)
            return NULL;
        // 如果有右边的孩子 则返回的结果是右子树的最左下角
        if(pNode->right!=NULL)
        {
            pNode=pNode->right;
            while(pNode->left!=NULL)
                pNode=pNode->left;
            return pNode;
        }
        // 如果没有右孩子
        while(pNode->next!=NULL){
            TreeLinkNode *parent=pNode->next;
            // 如果是父亲的左孩子 则 结果是父结点
            if(parent->left==pNode){
                return parent;
            }
            // 如果不是父亲的左孩子 则是父亲的右孩子
            // 此时结果应该以父亲作为pNode重新在向上找
            // 考以下三种情况
            // 一种是描述的例子的i结点 它的下一个应该是a所以应当返回a
            //     因为它是父节点e的右孩子 再看e结点 是e的父节点b的右孩子
            //     直到到了b 是父节点的a的左孩子 所以应该返回a
            // 第二种情况 自己画一下图 把例子图里面b下面两个子树对调换一下
            //     因为i是父节点e的右孩子 所以应该看e
            //     因为e是父节点b的左孩子所以 应该返回a
            // 第三种情况看g
            //     g是父节点c的右孩子 c是父节点a的右孩子 此时a到了根节点了，再往上没有了，则代表g是最后一个结点了，返回NULL
            pNode=pNode->next;
        }
        /*返回的是二叉树最后一个结点*/
        return NULL;
    }
};