给定树根root。实现中序遍历，也就是左根右。
用递归的话，很简单，左边的返回值加上root的再加上右边的就行。
我自己写的有点挫：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> lf, ri, ans;
if (root == NULL) return ans;
lf = inorderTraversal(root -> left);
ri = inorderTraversal(root -> right);
lf.push_back(root -> val);
for (int i = ; i < ri.size(); ++i)
{
lf.push_back(ri[i]);
}
return lf;
}
};
其实可以写简单一些：
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> vi;
inHelper(root, vi);
return vi;
}
void inHelper(TreeNode *node, vector<int>& vi)
{
if(node == nullptr) return;
inHelper(node->left, vi);
vi.push_back(node->val);
inHelper(node->right, vi);
}
};
题目要求如果不用递归的话，用如下leetcode上的，利用栈，很妙。
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> rs;
if (!root) return rs;
stack<TreeNode *> stk;
TreeNode *p = root;
while (!stk.empty() || p)
{
if (p)
{
stk.push(p);
p = p->left;
}
else
{
p = stk.top();
stk.pop();
rs.push_back(p->val);
p = p->right;
}
}
return rs;
}
2014-12-13
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> perm;
if (root == NULL) return perm;
stack<TreeNode *> sta; TreeNode *p = root; while(!sta.empty() || p)
{
while (p)
{
sta.push(p);
p = p -> left;
}
if (!sta.empty())
{
p = sta.top();
sta.pop();
perm.push_back(p -> val);
p = p -> right;
}
}
return perm;
}
};