算法—二叉树的前序遍历

知识点 树递归dfs广度优先搜索(BFS)

描述

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


数据范围：二叉树的节点数量满足 0≤n≤100 0 /le n /le 100 / 0≤n≤100  ，二叉树节点的值满足 1≤val≤100 1 /le val /le 100 / 1≤val≤100  ，树的各节点的值各不相同
 

示例 1：

示例1

输入：

{1,#,2,3}

返回值：

　　[1,2,3]

//方法1：

class Solution {
public:
    void preorder(vector<int> &res, TreeNode* root){
        //遇到空节点则返回
        if(root == NULL) 
            return;
        //先遍历根节点
        res.push_back(root->val); 
        //再去左子树
        preorder(res, root->left); 
        //最后去右子树
        preorder(res, root->right); 
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res; 
        //递归前序遍历
        preorder(res, root); 
        return res;
    }
};

方法一：递归（推荐使用）

知识点：二叉树递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res; 
        if(root == NULL)
            return res;
        //辅助栈
        stack<TreeNode*> s; 
        //根节点先进栈
        s.push(root); 
        //直到栈中没有节点
        while(!s.empty()){ 
            //每次栈顶就是访问的元素
            TreeNode* node = s.top(); 
            s.pop();
            res.push_back(node->val);
            //如果右边还有右子节点进栈
            if(node->right) 
                s.push(node->right);
            //如果左边还有左子节点进栈
            if(node->left) 
                s.push(node->left);
        }
        return res;
    }
};

方法二：非递归（扩展思路）

知识点：栈

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

思路：

我们都知道递归，是不断调用自己，计算内部实现递归的时候，是将之前的父问题存储在栈中，先去计算子问题，等到子问题返回给父问题后再从栈中将父问题弹出，继续运算父问题。因此能够递归解决的问题，我们似乎也可以用栈来试一试。

根据前序遍历“根左右”的顺序，首先要遍历肯定是根节点，然后先遍历左子树，再遍历右子树。递归中我们是先进入左子节点作为子问题，等左子树结束，再进入右子节点作为子问题。

这里我们同样可以这样做，它无非相当于把父问题挂进了栈中，等子问题结束再从栈中弹出父问题，从父问题进入右子树，我们这里已经访问过了父问题，不妨直接将右子节点挂入栈中，然后下一轮先访问左子节点。要怎么优先访问左子节点呢？同样将它挂入栈中，依据栈的后进先出原则，下一轮循环必然它要先出来，如此循环，原先父问题的右子节点被不断推入栈深处，只有左子树全部访问完毕，才会弹出继续访问。

具体做法：

• step 1：优先判断树是否为空，空树不遍历。
• step 2：准备辅助栈，首先记录根节点。
• step 3：每次从栈中弹出一个元素，进行访问，然后验证该节点的左右子节点是否存在，存的话的加入栈中，优先加入右节点。

图示：