题目描述

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

 

解题思路：

情况一、所给的节点的右子树不是空，则顺着找最小的

情况二、所给的节点右子树是空，且是左儿子则返回父节点

情况三、所给的节点右子树是空，且是右儿子且父亲是祖父的左儿子，则返回祖父节点

 

class Solution {public:    TreeLinkNode* getRoot(TreeLinkNode* pNode){        TreeLinkNode* root = NULL;        while(pNode != NULL){            root = pNode;            pNode = pNode->next;        }        return root;    }    TreeLinkNode* _getNext(TreeLinkNode* root, TreeLinkNode *pNode){        if(root == NULL) return NULL;//        cout<<"rval="<
     
      val<
      
       right != NULL){                //当前节点的右子树不是空则顺着找最左的节点                res = root->right;                while(res != NULL){                    if(res->left != NULL){                        res = res->left;                    }else{                        break;                    }                }            }else{                if(root->next != NULL){                    if(root->next->left == root){                        //如果当前节点的右子树为空且当前节点是左子树                        return root->next;                    }else if(root->next->right == root && root->next == root->next->next->left){                        //如果当前节点的右子树为空，当前节点是右子树且父节点是祖父的左子树                        return root->next->next;                    }                }            }//            cout<<"xxx"<
       
        left != NULL){                lRes = _getNext(root->left, pNode);            }            TreeLinkNode * rRes = NULL;            if(root->right != NULL){                rRes = _getNext(root->right, pNode);            }            if(lRes != NULL){                return lRes;            }else if(rRes != NULL){                return rRes;            }else{                return NULL;            }        }    }    TreeLinkNode* GetNext(TreeLinkNode* pNode)    {        TreeLinkNode *root = getRoot(pNode);        return _getNext(root, pNode);    }};