【leetcode100-036】【链表】二叉树中序遍历(四解)

发布时间:2024年01月16日

【题干】

给定一个二叉树的根节点?root?,返回?它的?中序?遍历?。

【思路】

由于题很简单,今天试试写多解,不然实在是太偷懒了。

  1. 递归:对任意非空节点执行“中序遍历左子树-visit自身-中序遍历右子树”
  2. 栈迭代:我认为本质上其实是模拟递归,或者说把递归的函数调用栈显式地写在了代码里面。对任意非空节点执行“有左子树时入栈并向左下行,无左子树时退栈visit并重新向右下行,无法下行时退栈visit并重新向右下行”。
  3. 栈迭代优化(着色法):从方法二可以看出,对一个有左子树的节点,我们第一次访问时用它拓展左子树,而当我们从它的左子树退出时才会在退栈时第二次访问它,并记录进结果中,对这个二次访问的动作,我们为每个节点添加一个颜色属性,在它第一次入栈时给它上色,而退栈时若遇到有色节点,则代表可以访问,借此简化了判断逻辑。
  4. Morris:如方法三分析,当我们访问完A节点的左子树时,做了两个动作,一个是从左子树上最后被访问的节点pre回到A节点,另一个是通过某种方式确定这是第二次访问到A节点,于是把A记录,Morris方法用一个动作解决了这两件事——把pre的right指针指向A,为什么这么做可以解决两件事呢?首先,回到了A,这不用解释了吧?其次,二次访问,当你找到一个A,发现它的pre已经指向了A,那肯定是之前曾经到过pre啊。而A作为pre的祖先,到过pre必然也到过A,本次显然至少是第二次访问A了,条件达成~当然这个方法在不允许修改原数据的情况下就会失效了......

怎么说呢,链表遍历毕竟还是太经典了,所以只是记录了一下关键思路,让我们来看代码吧。

【题解】

递归

class Solution {
public:
    void inorder(TreeNode* root, vector<int>& ans) {
        if (!root)
            return;
        inorder(root->left,ans);
        ans.push_back(root->val);
        inorder(root->right,ans);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        inorder(root, ans);
        return ans;
    }
};

迭代

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* cur =root;
        vector<int> ans;
        stack<TreeNode*> stk;
        while(cur||!stk.empty()){
            while(cur){
                stk.push(cur);
                cur=cur->left;
            }
            cur=stk.top();
            stk.pop();
            ans.push_back(cur->val);
            cur=cur->right;
        }
        return ans;
    }
};

着色

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<pair<TreeNode*,int> > stk;
        stk.push(make_pair(root,0));
        while(!stk.empty()){
            auto [node, color]=stk.top();
            stk.pop();
            if(node==nullptr)continue;
            if(color==0){
                stk.push(make_pair(node->right,0));
                stk.push(make_pair(node,1));
                stk.push(make_pair(node->left,0));
            }else{
                ans.push_back(node->val);
            }
        }
        return ans;
    }
};

Morris

class Solution {
public:
    TreeNode* getPredecessor(TreeNode* root){
        TreeNode* cur=root->left;
        while(cur->right&&cur->right!=root) cur=cur->right;
        return cur;
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        while(root){
            if(root->left){
                TreeNode* pre=getPredecessor(root);
                if(!pre->right){
                    pre->right=root;
                    root=root->left;
                }else{
                    ans.push_back(root->val);
                    root=root->right;
                    pre->right=nullptr;
                }
            }else{
                ans.push_back(root->val);
                root=root->right;
            }
        }
        return ans;
    }
};

文章来源:https://blog.csdn.net/weixin_63059689/article/details/135635893
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。