力扣题目链接:https://leetcode.cn/problems/binary-tree-preorder-traversal/
给你二叉树的根节点 root
,返回它节点值的 前序 遍历。
示例 1:
输入:root = [1,null,2,3] 输出:[1,2,3]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
示例 4:
输入:root = [1,2] 输出:[1,2]
示例 5:
输入:root = [1,null,2] 输出:[1,2]
提示:
[0, 100]
内-100 <= Node.val <= 100
进阶:递归算法很简单,你可以通过迭代算法完成吗?
前序遍历的遍历顺序是:
根 → 左子树 → 右子树
这很明显地是个递归。
因此,我们可以构造一个DFS
函数
void DFS(TreeNode* root);
来处理以root
为根时的遍历。
递归终止条件:root
为空。
函数内容:
先遍历得到这个节点的值,然后递归左子树,再递归右子树。
class Solution {
private:
vector<int> ans;
void dfs(TreeNode* root) {
if (!root) // 递归终止条件
return;
ans.push_back(root->val); // 先遍历得到这个节点的值
dfs(root->left); // 遍历左子树
dfs(root->right); // 遍历右子树
}
public:
vector<int> preorderTraversal(TreeNode* root) {
dfs(root); // 前序遍历
return ans;
}
};
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/126057536