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

二叉树的下一个结点

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

迭代法

使用栈来中序遍历,当节点值相同的时候,标志flag为true,再下一次拿到节点就是下一个节点并返回

注意由于传入的不一定是根节点,所以需要先拿到根节点

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
#include <stack>
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        //中序遍历
        stack<TreeLinkNode*> st;
        
        TreeLinkNode*cur=pNode;
        while (cur->next!=nullptr) {
            cur=cur->next;
        }

        //这里{5,4,#,3,#,2},4,出错的原因是传入的不是根节点,导致栈没有保存5
        bool flag=false;
        while(!st.empty()||cur!=nullptr){
            while(cur!=nullptr)
            {   
                st.push(cur);
                cur=cur->left;
            }

            cur=st.top();
            st.pop();
            if(flag){
                return cur;
            }
            if(cur->val==pNode->val)
            {
                flag=true;
            }
        
            cur=cur->right;
        }
        return nullptr;
    }
};

全部评论

相关推荐

面向对象的火龙果很爱...:去吃一顿炸鸡就走
点赞 评论 收藏
分享
积极的小学生不要香菜:你才沟通多少,没500不要说难
点赞 评论 收藏
分享
Twilight_m...:经典我朋友XXXX起手,这是那种经典的不知道目前行情搁那儿胡编乱造瞎指导的中年人,不用理这种**
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 10:39
一个证都没&nbsp;我能填什么
程序员小白条:别人有,你为什么没有,还是这个道理,社会就是比较,竞争,淘汰,你要安逸,那么就要做好淘汰的准备
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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