二叉树的前序遍历

题目描述

给定二叉树的根节点root，返回它的节点值的前序遍历。

输入输出样例

Input: root = [1,null,2,3]
Output: [1,2,3]

题解

对于二叉树遍历，我们常使用的两种方法：递归、迭代(非递归)
一、递归方法三步走：

1. 确定递归的返回类型与函数参数

   • 仅是用于处理数据，因此我们不需要返回数据
   • 需要二叉树，并将它的节点存入数组.
   • 参数为(TreeNode * root, vectorres)

     void build(TreeNode* root, vector<int>& res)

2. 确定递归的终止条件

   • 当节点为空时，那么本层的递归就结束了

     if (root == nullptr) return;

3. 确定单层递归的逻辑

   • 前序遍历的顺序是:中－》左－》右
   • 所以应先取中间节点的值

     res.push_back(root->val);
     build(root->left);
     build(root->right);

这样的二叉树前序遍历结束了，完整的代码如下：

class Solution {
public:
    void build(TreeNode* root,vector<int>& res) {
        // 确定递归终止条件
        if (root == nullptr) return;

        // 确定单层递归的逻辑
        res.push_back(root->val);
        build(root->left,res);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        build(root,res);
        return res;
    }
};

二、前序遍历的迭代法
前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，再将右节点入栈，最后再将左节点入栈。根据这个逻辑，我们可以轻松写出代码。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> windows;
        vector<int> res;
        if (root == nullptr) return res;
        windows.push(root);

        while (!windows.empty()) {
            TreeNode* node = windows.top();
            windows.pop();
            res.push_back(node->val);
            if (node->right) windows.push(node->right);
            if (node->left) windows.push(node->left);
        }
        return res;
    }
};