[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?

1. 递归解法：

连题目都说recursive solution is trivial，没啥好说的，这解法两分钟写不出来就要被鄙视了。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: vector<int> inorderTraversal(TreeNode *root) { vector<int> allNodeValues; inorderTrav(root, allNodeValues); return allNodeValues; } void inorderTrav(TreeNode *root, vector<int> &allNodeValues) { if(!root) return; inorderTrav(root->left, allNodeValues); allNodeValues.push_back(root->val); inorderTrav(root->right, allNodeValues); } };

2. 迭代解法：

面试中应该不会只考递归这么简单。所以迭代解法才是真正的重点。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public: vector<int> inorderTraversal(TreeNode *root) { vector<int> allNodeValues; TreeNode *cur = root; stack<TreeNode*> s; while(cur || !s.empty()) { if(!cur) { cur = s.top(); s.pop(); allNodeValues.push_back(cur->val); cur = cur->right; } else { s.push(cur); cur = cur->left; } } return allNodeValues; } };