Given a binary tree, return the inorder traversal of its nodes‘ values. （Medium）
For example:
Given binary tree [1,null,2,3],
1
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
分析：
太经典基础的算法问题了，但想写出一个无bug的非递归二叉树中序遍历也不是很容易。先看递归版本的代码：
1 class Solution { 2 private: 3 vector<int> result; 4 void helper(TreeNode* root) { 5 if (root == nullptr) { 6 return; 7 } 8 helper(root -> left); 9 result.push_back(root -> val); 10 helper(root -> right); 11 } 12 public: 13 vector<int> inorderTraversal(TreeNode* root) { 14 helper(root); 15 return result; 16 } 17 };
再考虑非递归，其实就是对于每个节点，走到最左端，沿路径压栈。
到达最左端后以此返回，开始弹栈，对于每个弹出的元素，记录其value，并且走向其右节点重复上述过程（走到最左端...）。
直到栈内元素为空为止。
代码：
1 class Solution { 2 public: 3 vector<int> inorderTraversal(TreeNode* root) { 4 vector<int> result; 5 stack<TreeNode*> s; 6 TreeNode* p = root; 7 while (p || !s.empty()) { 8 while (p != nullptr) { 9 s.push(p); 10 p = p -> left; 11 } 12 if (!s.empty()) { 13 p = s.top(); 14 result.push_back(p -> val); 15 s.pop(); 16 p = p -> right; 17 } 18 } 19 return result; 20 } 21 };
LeetCode94 Binary Tree Inorder Traversal
原文：http://www.cnblogs.com/wangxiaobao/p/5998449.html