Leetcode145:

Binary Tree Postorder Traversal: Given a binary tree, return the postorder traversal of its nodes’ values. Example: Input: [1,null,2,3] Output: [3,2,1]

Solution:

#include <iostream> #include <stack> #include <vector> #include <string> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; struct Command{ string s; TreeNode* node; Command(string s, TreeNode* node): s(s), node(node){} }; // 后序遍历二叉树的非递归实现 class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> res; if ( root == NULL ) return res; stack<Command> stack; stack.push( Command("go", root) ); while ( !stack.empty() ){ Command command = stack.top(); stack.pop(); if( command.s == "print" ) res.push_back( command.node -> val ); else{ assert( command.s == "go" ); stack.push( Command("print", command.node) ); if( command.node -> right ) stack.push( Command("go", command.node -> right) ); if( command.node -> left ) stack.push( Command("go", command.node -> left) ); } } return res; } };

总结： 上述解法是非递归的实现的后序遍历，用了栈的思想，模拟系统栈的工作流程。递归方法简单，就不实现了。