Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree{1,#,2,3}, 1 \ 2 / 3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
解法一：递归
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector inorderTraversal(TreeNode *root) { vector ret; if(!root) return ret; inorder(root, ret); return ret; } void inorder(TreeNode* root, vector & ret) { if(root->left) inorder(root->left, ret); ret.push_back(root->val); if(root->right) inorder(root->right, ret); }}; 
解法二：非递归
使用map记录是否访问过，使用栈记录访问路径，访问过就出栈。
遵循左根右原则。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector inorderTraversal(TreeNode *root) { vector ret; if(!root) return ret; stack stk; unordered_map m; stk.push(root); m[root] = true; while(!stk.empty()) { TreeNode* top = stk.top(); if(top->left) { if(m[top->left] == false) { stk.push(top->left); m[top->left] = true; continue; } } ret.push_back(top->val); stk.pop(); if(top->right) { if(m[top->right] == false) { stk.push(top->right); m[top->right] = true; } } } return ret; }}; 
解法三：非递归，不需要除栈之外的空间
每次新加入节点时，将左子节点（比当前节点小）全部进栈，这样在出栈的时候就不需要再去访问左子节点，
只需要访问右子节点（比当前节点大）
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector inorderTraversal(TreeNode* root) { vector ret; if(root == NULL) return ret; stack stk; stk.push(root); TreeNode* cur = root; while(cur->left) { stk.push(cur->left); cur = cur->left; } while(!stk.empty()) { TreeNode* top = stk.top(); stk.pop(); ret.push_back(top->val); if(top->right) { TreeNode* cur = top->right; stk.push(cur); while(cur->left) { stk.push(cur->left); cur = cur->left; } } } return ret; }}; 