hot100---day3

二叉树复习+hot100专题

144. 二叉树的前序遍历 - 力扣（LeetCode）

递归法的前中后序遍历，格式比较一致；

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

    }
};

94. 二叉树的中序遍历 - 力扣（LeetCode）

中序遍历；左中右；

class Solution {
public:
    // void traversal(TreeNode* cur, vector<int>& v)
    // {
    //     if(cur==nullptr) return;
    //     traversal(cur->left,v);
    //     v.push_back(cur->val);
    //     traversal(cur->right,v);
    // }
    void traversal(TreeNode* node, vector<int>& nums)
    {
        if(node==nullptr) return;
        TreeNode* cur = node;
        traversal(cur->left, nums);
        nums.push_back(cur->val);
        traversal(cur->right, nums);
    }
    vector<int> inorderTraversal(TreeNode* root) {
       vector<int> nums;
       traversal(root, nums);
       return nums;
    }
};

145. 二叉树的后序遍历 - 力扣（LeetCode）

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

递归法：

前序遍历；

思路：利用数据结构栈来实现，前序，中左右，所以碰到的栈顶元素就需要push_back到数组中去；然后对于左右节点，是右节点先进入，然后左节点，这样弹出的时候才是左节点先弹出，然后右节点弹出；

class Solution {
public:

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(root==nullptr) return ans;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty())
        {
            auto tmp = st.top();
            st.pop();
            ans.push_back(tmp->val);
            if(tmp->right) st.push(tmp->right);
            if(tmp->left) st.push(tmp->left);
        }
        return ans;

    }
};