算法题-二叉树的中序遍历-爱代码爱编程
C++解二叉树的中序遍历
原题:
给定一个二叉树的根节点 root ,返回它的 中序 遍历。
示例 1:
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
示例 4:
输入:root = [1,2]
输出:[2,1]
示例 5:
输入:root = [1,null,2]
输出:[1,2]
提示:
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal
解题:对于这道题,首先需要先了解二叉树的中序遍历是指什么,就是按照左子树-根节点-右子树的顺序进行访问,其中对于左子树的遍历,同样是按照这样子的方法进行的。那么对于这样的规律,我们就可以利用递归来实现了。首先给出递归的出口,就是当遍历的这个节点为空时,那就要返回,退出递归。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
order(root,ans);
return ans;
}
void order(TreeNode* root,vector<int>& ans){
if(!root){
return;
}
order(root->left,ans);
ans.push_back(root->val);
order(root->right,ans);
}
};