Leetcode之144. 二叉树的前序遍历

递归解法

执行结果：

解题思路：

• 推荐b站讲递归原理的视频：https://www.bilibili.com/video/BV1fZ4y1p7M9?spm_id_from=333.999.0.0
• 前序遍历、中序遍历、后续遍历，仅需更改void函数的遍历顺序即可；

语言：C++

class Solution {
public:
    //注意，这里是void声明postorder函数
    void preorder(TreeNode* root, vector<int> &res) {
        //树为空的情况
        if(root == nullptr){return;}

        //遍历顺序，前序遍历、中序遍历、后序遍历仅改此处次序
        res.push_back(root->val);//根
        preorder(root->left,res);//左
        preorder(root->right,res);//右

    }

    //主函数
    vector<int> preorderTraversal(TreeNode* root) {
        //存放结果
        vector<int> res;

        //递归postorder函数
        preorder(root,res);
        
        //返回结果
        return res;
    }
};

迭代解法

执行结果：

解题思路：

• 推荐b站15分钟二叉树非递归解法视频：https://www.bilibili.com/video/BV1RP4y1G79Z?spm_id_from=333.337.search-card.all.click
• 前面的讲解也挺好，最好听一下。
• 下图为代码梳理：
  

语言：C++

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==nullptr){return res;}

        stack<TreeNode*> stk;
        TreeNode* cur=root;

        while(!stk.empty()||cur!=nullptr){
            while(cur!=nullptr){
                //根
                res.emplace_back(cur->val);
                //左
                stk.emplace(cur);
                cur=cur->left;
            }
            
            //右
            cur=stk.top();
            stk.pop();
            cur=cur->right;
        }

        return res;
    }
};

细节提升 1.迭代与递归

• 迭代是循环反馈过程的活动。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。
• 递归指的是不断引用自身，直到引用的唯一已知对象时止的过程。

2.栈的基本 *** 作

• pop是从栈中d出最上面的元素并取得它；
• top是取得栈最上面的元素（但不让它d出，这个元素还在栈内）；
• push是压入一个元素；
• empty是判断栈是否空的；
• makeempty是把栈清空。

3.emplace_back()与push_back()

push_back()方法要调用构造函数和复制构造函数，这也就代表着要先构造一个临时对象，然后把临时的copy构造函数拷贝或者移动到容器最后面。
而emplace_back()在实现时，则是直接在容器的尾部创建这个元素，省去了拷贝或移动元素的过程。