LeetCode: 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?
地址：https://oj.leetcode.com/problems/binary-tree-inorder-traversal/
算法：要求用非递归来进行中序遍历。初始时，从根节点开始，一直往左走，并把每个节点入栈。在while循环内，取栈顶元素，出栈，访问该元素，若该元素有右孩子，往右走，在一直往左走到低并把每个节点进栈，如此循环知道栈为空。代码：
1 /**
2 * Definition for binary tree
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 vector<int> inorderTraversal(TreeNode *root) {
13 vector<int> result;
14 if(!root) return result;
15 TreeNode *p = root;
16 stack<TreeNode*> stk;
17 while(p){
18 stk.push(p);
19 p = p->left;
20 }
21 while(!stk.empty()){
22 p = stk.top();
23 stk.pop();
24 result.push_back(p->val);
25 p = p->right;
26 while(p){
27 stk.push(p);
28 p = p->left;
29 }
30 }
31 return result;
32 }
33 };
LeetCode: Binary Tree Inorder Traversal
原文：http://www.cnblogs.com/boostable/p/leetcode_binary_tree_inorder_traversal.html