题解 | #二叉树的前序遍历#

二叉树的前序遍历

http://www.nowcoder.com/practice/5e2135f4d2b14eb8a5b06fab4c938635

题目的主要信息：

给定一颗二叉树的根节点，输出其前序遍历的结果

方法一：递归

具体做法：

什么是二叉树的前序遍历？简单来说就是“根左右”，展开来说就是对于一颗二叉树优先访问其根节点，然后访问它的左子树，等左子树全部访问完了再访问其右子树，而对于子树也按照之前的访问方式，直到到达叶子节点。

从上述前序遍历的解释中我们不难发现，它存在递归的子问题：每次访问一个节点之后，它的左子树是一个要前序遍历的子问题，它的右子树同样是一个要前序遍历的子问题。那我们可以用递归处理：

终止条件： 当子问题到达叶子节点后，后一个不管左右都是空，因此遇到空节点就返回。
返回值： 每次处理完子问题后，就是将子问题访问过的元素返回，依次存入了数组中。
本级任务： 每个子问题优先访问这棵子树的根节点，然后递归进入左子树和右子树。

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;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，其中 $n$ 为二叉树的节点数，遍历二叉树所有节点
空间复杂度： $O (n)$ ，最坏情况下二叉树化为链表，递归栈深度为 $n$

方法二：非递归

具体做法：

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

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

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

具体过程可以参考如下：

alt

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;
    }
};

复杂度分析：