1. 问题形容:
给出一棵二叉树,返回其节点值的前序遍历。
提醒:前序排列的定义:根节点——左子树——右子树的形式遍历这棵树
2. 解题思路:
在这道题目当中最好了解的就是应用递归的算法, 首先咱们须要理解什么是二叉树的前序遍历:依照拜访根节点——左子树——右子树的形式遍历这棵树,而在拜访左子树或者右子树的时候,咱们依照同样的形式遍历,直到遍历完整棵树。因而整个遍历过程人造具备递归的性质,咱们能够间接用递归函数来模仿这一过程。
定义 preorder(root) 示意以后遍历到 root 节点的答案。依照定义,咱们只有首先将 root 节点的值退出答案,而后递归调用 preorder(root.left) 来遍历 root 节点的左子树,最初递归调用 preorder(root.right) 来遍历 root 节点的右子树即可,递归终止的条件为碰到空节点。
3. 解题代码
class Solution {
public:
void preorder(TreeNode *root, vector<int> &res) {if (root == nullptr) {return;}
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
vector<int> preorderTraversal(TreeNode *root) {
vector<int> res;
preorder(root, res);
return res;
}
};