leetcode 94. 二叉树的中序遍历(C++)

淡淡的烟草味﹌ 2023-05-28 14:20 17阅读 0赞

给定一个二叉树，返回它的中序遍历。

示例:

输入: [1,null,2,3]
       1
        \
         2
        /
       3
    
    输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：[94. 二叉树的中序遍历 - 力扣（LeetCode）][94. _ - _LeetCode]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 递归法 #

*  递归将树中节点按左根右的顺序加入队列

代码如下：

class Solution { 
    public:
        vector<int> nodes;
        vector<int> inorderTraversal(TreeNode* root) { 
            iTraversal(root);
            return nodes;
        }
        void iTraversal(TreeNode* root){ 
            if(root->left)  iTraversal(root->left);
            nodes.push_back(root->val);
            if(root->right)  iTraversal(root->right);
        }
    };

结果：  
![在这里插入图片描述][20200322004617869.png]

# 迭代法 #

*  利用栈储存节点实现左根右顺序的迭代  
    先将根节点存入栈，然后执行如下循环，直至栈中没有节点剩余：  
    （1）读取（不出栈）栈顶元素，若它有左子树，将其左子树节点存入栈，直接进入下一轮循环  
    （2）若它没有左子树，则将其值存入输出列表，并将其出栈  
    （3）若它（还是之前的栈顶元素）有右子树，将其右子树节点存入栈

代码如下：

class Solution { 
    public:
        vector<int> inorderTraversal(TreeNode* root) { 
            vector<int> nodes{ };
            if(!root)   return nodes;
            vector<TreeNode*> list{ root};
            while(!list.empty()){ 
                auto node = list.back();
                if(node->left){ 
                    list.push_back(node->left);
                    node->left = NULL;
                    continue;
                }  
                nodes.push_back(node->val);
                list.pop_back();
                if(node->right)  list.push_back(node->right);
            }
            return nodes;
        }
    };

结果：  
![在这里插入图片描述][20200322161137128.png]

[94. _ - _LeetCode]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal
[20200322004617869.png]: /images/20230528/af2ae0a596104d9583790af7158e7dfc.png
[20200322161137128.png]: /images/20230528/5ed4feae0c3b4db99e26a2c93049037f.png