Given a binary tree, return the inorder traversal of its nodes' values.
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?
解题思路:
二叉树的遍历是基础，具体至少应该掌握递归遍历和迭代遍历，遍历又分别前序遍历，中序遍历和后续遍历。代码如下：
递归方法：
class Solution {
public:
void getInorderData(TreeNode* root, vector<int> & ret)
{
if(root == NULL) return;
if(root->left != NULL) getInorderData(root->left,ret);
ret.push_back(root->val);
if(root->right != NULL) getInorderData(root->right,ret);
return;
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ret;
getInorderData(root,ret);
return ret;
}
};
迭代版本：
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ret;
stack<TreeNode*> stk;
TreeNode* curr = root;
while(!stk.empty() || curr)
{
if(curr)
{
stk.push(curr);
curr = curr->left;
}else
{
curr = stk.top();
ret.push_back(curr->val); //永远在当前节点是根节点的时候取值
stk.pop();
curr = curr->right;
}
}
return ret;
}
};
参考资料：https://discuss.leetcode.com/topic/3288/three-methods-to-solve-c
