一、题目
二、思路和题解
1.思路
递归确实简单,思考步骤归纳如下:
- 确定递归函数的参数个数和返回值
- 确定终止条件
- 确定单层递归的逻辑
注意:只考虑单层的递归逻辑,细想其他步骤容易把自己绕进去。
本题中序遍历顺序是'左根右'。
- 返回数组,参数为节点指针。
- 终止条件:当前指针指向 null。
- 单层逻辑:先递归左孩子,再访问根节点,最后递归右孩子。
2.代码(递归)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void traversal(vector<int>& res, TreeNode* root) {
if (root != nullptr) {
traversal(res, root->left); // 先看左孩子
res.push_back(root->val); // 读根节点
traversal(res, root->right);// 看右孩子
}
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
traversal(res, root);
return res;
}
};
补充前序遍历(根左右)和后序遍历(左右根)的写法。
前序遍历:
class Solution {
public:
vector<int> preorderTraversal {
vector<> res;
(root, res);
res;
}
{
(node == ) ;
res.(node->val);
(node->left, res);
(node->right, res);
}
};


