力扣144.二叉树的前序遍历_力扣二叉树的前序遍历

**

144. 二叉树的前序遍历

**

给你二叉树的根节点 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  
进阶：递归算法很简单，你可以通过迭代算法完成吗？
通过次数435,443提交次数618,360
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

按照二叉树的遍历就是先进行左子树的遍历，然后再进行右子树的遍历.对于每一个节点的思路都是这样进行.
那么解决这个题目就可以分为三个部分.
①遍历根节点，加入根节点是nullptr那就返回空，如果不空，那就将结果存储进数组
②遍历该节点的左子树，把每次遍历的结果存储进数组
③遍历该节点的右子树，把每次遍历的结果存储进数组

代码如下：

/**
 * 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 getDeepOne(TreeNode *root, vector<int> &resNums) {
        if (root == nullptr) {
            return ;
        }
        resNums.push_back (root->val);
        getDeepOne(root -> left, resNums);
        getDeepOne(root -> right, resNums);

    }

    //用于创建一个返回值得函数，并且调用一个递归得开始
    vector<int> preorderTraversal(TreeNode* root) {
         vector<int> resNums;
         getDeepOne(root, resNums);
         return resNums;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

运行结果如下：