One algorithm of the day — Leetcode 145– python&C++

【 topic description 】

【 Idea 1: Iteration 】

Iterating with stacks, you can take two stacks, or you can take one stack and then output the structure backwards. The root node is pushed first, then enters the while loop, pops the top element and saves the value in a list RE, then pushes the left and right children of the top element in turn, and continues the loop. Just reverse the RE.

C++:
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> stack;
        vector<int> re;
        if(! root){returnre; } stack.push(root);while(! stack.empty()){ TreeNode* top=stack.top(); stack.pop(); re.push_back(top->val);if(top->left){stack.push(top->left); }if(top->right){stack.push(top->right); } } vector<int> re2;for(int i=re.size()-1; i>=0; i--){ re2.push_back(re[i]); }returnre2; }};Copy the code

python3:
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        re=[]
        if not root:
            return []
        stack=[root]
        while stack:
            top=stack.pop()
            re.append(top.val)
            if top.left:
                stack.append(top.left)
            if top.right:
                stack.append(top.right)
        return re[::-1]
Copy the code

【 idea 2: Recursion 】

The recursion is so simple, I won’t say much, but I’ll just look at the code.

C++:
class Solution {
public:
    vector<int> re;
    vector<int> postorderTraversal(TreeNode* root) {
        dfs(root);
        return re;
    }
    void dfs(TreeNode* root){
        if(root){ dfs(root->left); dfs(root->right); re.push_back(root->val); }}};Copy the code

python3:
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        self.re=[]
        self.dfs(root)
        return self.re

    def dfs(self,root):
        if root:
            self.dfs(root.left)
            self.dfs(root.right)
            self.re.append(root.val)
Copy the code