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

二叉树的下一个结点

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:
    vector<TreeLinkNode*> v;
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        TreeLinkNode* r = pNode;
        while(r->next)//找到根节点
            r = r->next;
        inorder(r);
        for(int i = 0;i < v.size();++i){
            if(v[i] == pNode && i+1 < v.size())
                return v[i+1];
        }
        return NULL;
    }
    void inorder(TreeLinkNode* r){
        if(!r)return;
        inorder(r->left);
        v.push_back(r);
        inorder(r->right);
    }
};

方法二:

分情况:

	 如果有右子树,那么中序的下一个为右子树的最后一个左子树
     如果没有右子树,判断节点在树的左子树还是右子树,如果左子树那么下一个就是它的父节点中的一个。如果在右为空。
/*
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->right){//有右节点,即右节点的左子树即下一个节点
            pNode = pNode->right;
            while(pNode->left)
                pNode = pNode->left;
            return pNode;
        }
        while(pNode->next){//判断当前在树的左树还是右树
            if(pNode->next->left == pNode)//如果在左树
                return pNode->next;
            pNode = pNode->next;
        }
        return NULL;
    }
};
全部评论

相关推荐

这是什么操作什么意思,这公司我服了...
斯派克spark:意思是有比你更便宜的牛马了
点赞 评论 收藏
分享
能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
半解316:内容充实,细节需要修改一下。 1,整体压缩为一页。所有内容顶格。 2,项目描述删除,直接写个人工作量 修改完之后还需要建议,可以私聊
点赞 评论 收藏
分享
投递长鑫存储等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务