Binary Tree Inorder Traversal.png
解題思路 ：
- post order 的 recursive 解法 left, self, right
- 如果要使用 iterative 的做法 可以用 stack 來做 先用 root 檢查 只要有 left child 就一層一層把所有 left child 都放入 stack 然後再拿 top 出來放入 result 之後檢查從 stack 出來的 node 的 right child 是否有左邊子節(jié)點(diǎn) 繼續(xù)做相同的步驟
C++ code :
<pre><code>
//Recursive
class Solution {
/**
* @param root: The root of binary tree.
* @return: Inorder in vector which contains node values.
*/
public:
void inOrder(TreeNode *root, vector<int> &res)
{
if(root == nullptr) return;
inOrder(root->left, res);
res.emplace_back(root->val);
inOrder(root->right, res);
}
vector<int> inorderTraversal(TreeNode *root) {
// write your code here
vector<int> res;
inOrder(root, res);
return res;
}
};
//Iterative
class Solution {
/**
* @param root: The root of binary tree.
* @return: Inorder in vector which contains node values.
*/
public:
vector<int> inorderTraversal(TreeNode *root) {
// write your code here
vector<int> res;
if(root == nullptr) return res;
stack<TreeNode*> s;
TreeNode *cur = root;
while(cur || !s.empty())
{
while(cur)
{
s.push(cur);
cur = cur->left;
}
cur = s.top();
s.pop();
res.emplace_back(cur->val);
cur = cur->right;
}
return res;
}
};
