Leetcode94:

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

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> inorderTraversal(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" ); if( command.node -> right ) stack.push( Command("go", command.node -> right) ); stack.push( Command("print", command.node) ); if( command.node -> left ) stack.push( Command("go", command.node -> left) ); } } return res; } };

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