LeetCode 145. Binary Tree Postorder Traversal

LeetCode 145. Binary Tree Postorder Traversal：题目、思路与代码实现。

对树的内容有点遗忘了，做一道常见的后序遍历的题目来温习一下

题目

Given a binary tree, return the postorder traversal of its nodes’ values.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

题解

这题用递归解法很简单，但做这题主要的目的就是为了复习循环实现的后序遍历

递归实现

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    if(root == NULL) return result; // special case
    
    recurse(root, result);
    return result;
}

void recurse(TreeNode* node, vector<int> &result){
    if(node == NULL) return;
    recurse(node->left, result);
    recurse(node->right, result);
    result.push_back(node->val);
}

循环实现

这一种实现方法其实是 “逆后序遍历” 的感觉，回头再尝试有没办法正儿八经地模拟函数递归进行正向迭代。

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    if(root == NULL) return result; // special case
    
    interate(root, result);
    return result;
}
void iterate(TreeNode* root, vector<int> &result){
    stack<TreeNode*> s;
    s.push(root);
    while(!s.empty()) { 
        TreeNode* ele = s.top();
        s.pop(); 
        if(ele->left != NULL) 
            s.push(ele->left); 
        if(ele->right != NULL)
            s.push(ele->right);
        result.insert(result.begin(), ele->val); 
    }
}

---

本文最初发布于简书。

Donate