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

二叉树的下一个结点

http://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e

/*
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){//当前节点有右子树时
            TreeLinkNode* mostLeft=pNode->right;
            while(mostLeft->left){//一直往左下走
                mostLeft=mostLeft->left;
            }
            return mostLeft;
        }
        else{//说明当前节点没有右子树
            //此时往上找节点是其父节点的左孩子的节点,这个节点的父节点就是要找的节点
            TreeLinkNode* parent=pNode->next;//父节点
            while(parent&&parent->right==pNode){
                pNode=parent;
                parent=parent->next;//往上继续找
            }
            if(parent){
                return parent;
            }
            else{
                return NULL;
            }
        }
        return NULL;
    }
    
};
全部评论

相关推荐

听说改名字就能收到offer哈:Radis写错了兄弟
点赞 评论 收藏
分享
Noob1024:一笔传三代,人走笔还在
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务