【力扣总结】LeetCode二叉树打卡day4（C++代码）

递归的三要素：

• 递归函数的参数和返回值
• 确定终止条件
• 确定单层循环的逻辑

思路1：递归

前序遍历：根节点-左子树-右子树

• 递归函数的参数和返回值：因为要对二叉树进行遍历，所以参数里应当有当前遍历到的根节点root。要将结果保存在vector里，还应该有答案的集合ans
• 确定终止条件：如果当前节点为空，说明该节点没有子节点了，直接返回即可。
• 确定单层循环的逻辑：先将当前节点存入答案里，然后递归遍历左子树和右子树

代码1：

class Solution {
public:
    void dfs(TreeNode* root,vector&ans){
        if(root==nullptr) return ;
        ans.push_back(root->val);
        dfs(root->left,ans);
        dfs(root->right,ans);
    }
    vector preorderTraversal(TreeNode* root) {
        vectorans;
        dfs(root,ans);
        return ans;
    }
};

思路2：非递归

栈的特点：先进后出

递归的本质是深度优先搜索，先独立的搜索完左子树再去搜索右子树。

所以在放入栈的时候应当先加入右儿子再加入左儿子，这样左儿子先出栈，并且继续遍历左子树，最终左子树再右子树前面。

代码：

class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
        vectorans;
        stackstk;
        if(!root) return ans;
        stk.push(root);
        while(!stk.empty()){
            TreeNode* now=stk.top();stk.pop();
            ans.push_back(now->val);
            if(now->right) stk.push(now->right);
            if(now->left) stk.push(now->left);
        }
        return ans;
    }
};

思路1：递归

中序遍历：左子树-根节点-右子树

代码1：

class Solution {
public:
    void dfs(TreeNode* root,vector&ans){
        if(root==nullptr) return ;
        dfs(root->left,ans);
        ans.push_back(root->val);
        dfs(root->right,ans);
    }
    vector inorderTraversal(TreeNode* root) {
        vectorans;
        dfs(root,ans);
        return ans;
    }
};

思路1：递归

后序遍历：左子树-右子树-根节点

代码1：

class Solution {
public:
    void dfs(TreeNode* root,vector&ans){
        if(root==nullptr) return ;
        dfs(root->left,ans);
        dfs(root->right,ans);
        ans.push_back(root->val);
    }
    vector postorderTraversal(TreeNode* root) {
        vectorans;
        dfs(root,ans);
        return ans;
    }
};

思路2：非递归

后序遍历是左右根，反转后是根右左，所以在入栈的时候先入左儿子。（跟前序遍历对比看）

代码2：

class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        vectorans;
        stackstk;
        if(!root) return ans;
        stk.push(root);
        while(!stk.empty()){
            TreeNode* now=stk.top();stk.pop();///根右左
            if(now->left) stk.push(now->left);
            if(now->right) stk.push(now->right); 
            ans.push_back(now->val);    
        }
        reverse(ans.begin(),ans.end());
        return ans;//左右根
    }
};