二叉树的前序遍历

忘是亡心i 2022-10-22 04:07 187阅读 0赞

**二叉树文章系列：**

1.  [二叉树的前序遍历][Link 1]
2.  [二叉树的中序遍历][Link 2]
3.  [二叉树的后序遍历][Link 3]
4.  [二叉树的层序遍历][Link 4]
5.  [二叉树的前序、中序、后序、层序遍历【解法完整版】][Link 5]

### 本文目录 ###

*   *  一、解题思路：递归
     *  二、解题思路：迭代（方法1）
     *  三、解题思路：迭代（方法2）

![3f6957d485721213ec35be97bbe89d42.png][]

二叉树的前序遍历的记忆法则是“根左右"，即先遍历根节点，再遍历左子树节点，再遍历右子树节点。

以上图为例，前序遍历的结果是【A, B, D, E, C, F, G】

## 一、解题思路：递归 ##

递归是我们实现前中后序遍历最常用的方法。

> 什么问题可以采用递归求解呢？
> 
> 需要满足三个条件：
> 
> 1.  一个问题的解可以分解为若干个子问题的解；
> 2.  这个问题与分解的子问题，除了数据规模不同外，求解思路相同
> 3.  存在递归终止条件。
> 
> 那么在知道一个问题可以采用递归实现之后，如何写出递归代码呢？
> 
> 关键在于**能写出递归公式，找到终止条件。**

在二叉树的前序遍历问题上，它的递归公式是:

> preorder(node) = print node —> preorder(node->left) --> preorder(node->right)

它的终止条件是：

> node 是否为空，为空则返回。

class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
            vector<int> res;
            preorder(res, root);
            return res;
        }
    
        void preorder(vector<int>& res, TreeNode* root){
            
            if(!root) return;
            res.emplace_back(root->val);
            preorder(res, root->left);
            preorder(res, root->right);
        }
    };

## 二、解题思路：迭代（方法1） ##

在递归方法实现过程中，它的底层是基于系统栈的结构来实现的。因此，我们可以使用栈的数据结构来辅助实现基于迭代方式的前序遍历。

具体思路为：

*  初始化栈stack，初始化输出列表res
 *  根节点入栈
 *  while(栈不为空)，在循环体内部：
    
     *  栈顶元素出栈
     *  栈顶元素添加到输出列表
     *  如果栈顶元素的右子树节点不为空，将右子树节点入栈
     *  如果栈顶元素的左子树节点不为空，将左子树节点入栈
 *  返回输出列表res

![1ba3fde59cacd4da596ae47b6bd45a72.png][]

class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
    
            vector<int> res;
            if(!root) return res;
    
            stack<TreeNode*> s;
            s.push(root);
    
            while(!s.empty()){
                TreeNode* node = s.top();
                s.pop();
                res.emplace_back(node->val);
    
                if(node->right) s.push(node->right);
                if(node->left) s.push(node->left);
            }
    
            return res;
    
    
        }
    };

## 三、解题思路：迭代（方法2） ##

基于迭代方法的第二种思路如下：

*  初始化栈stack，初始化输出列表res
 *  设置一个变量cur, 表示当前节点。并赋初始值为根节点root
 *  while(栈不为空 或者 当前节点cur不为空)，在循环体内部：
    
     *  沿着当前节点的左分支一直走，直到为空。在这个过程中将遍历的节点都入栈，同时添加到输出列表
     *  栈顶元素出栈
     *  更新当前节点cur为栈顶元素的右子树节点。
 *  返回输出列表res

以图中的二叉树为例，来一步步来展示这个过程：

![3f6957d485721213ec35be97bbe89d42.png][]

初始时，当前节点cur = root ，即节点A  
![0aaf1c5744a4cb5f7735360a9d471eb5.png][]  
![8836fca4c3b3c0fe3c8cd98aadb0b5dd.png][]  
![e0450a1001ffd5edcdc28d227859e42e.png][]  
![b8cec7f3549d2a6c0ffebe34ab5234a1.png][]  
![db9605dfd53486369c75416e87310104.png][]  
![4028f0670372088475cbb5678fc54990.png][]  
![73818f1984922e768818a2fd786f68f3.png][]

class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
    
            vector<int> res;
            if(!root) return res;
    
            TreeNode* cur = root;
            stack<TreeNode*> s;
            while(!s.empty() || cur){
                // 沿着当前节点cur的左分支一直走到底
                while(cur){
                    s.push(cur);
                    res.emplace_back(cur->val);
                    cur = cur->left;
                }
                TreeNode* node = s.top();
                s.pop();
                cur = node->right;
            }
            return res;
    
        }
    };

[Link 1]: https://blog.csdn.net/u010414589/article/details/115415226
[Link 2]: https://blog.csdn.net/u010414589/article/details/115415373
[Link 3]: https://blog.csdn.net/u010414589/article/details/115415388
[Link 4]: https://blog.csdn.net/u010414589/article/details/114905914
[Link 5]: https://blog.csdn.net/u010414589/article/details/115415401
[3f6957d485721213ec35be97bbe89d42.png]: /images/20221022/a955ed568e844050a999c3691bf5619f.png
[1ba3fde59cacd4da596ae47b6bd45a72.png]: /images/20221022/193cc2ed95754896918d25171afc5759.png
[0aaf1c5744a4cb5f7735360a9d471eb5.png]: /images/20221022/52600d5ab4814ae491b150a59c583f09.png
[8836fca4c3b3c0fe3c8cd98aadb0b5dd.png]: /images/20221022/ffe05a0e71fa458dbcd7f04c1356e122.png
[e0450a1001ffd5edcdc28d227859e42e.png]: /images/20221022/fd6dd0d0e1b549089ec5db1672b47b82.png
[b8cec7f3549d2a6c0ffebe34ab5234a1.png]: /images/20221022/3328933627e047cd845f8596f512c982.png
[db9605dfd53486369c75416e87310104.png]: /images/20221022/b7d4408a5bdd4ab2ab89e3fcb5fe0425.png
[4028f0670372088475cbb5678fc54990.png]: /images/20221022/23960d42398848ce951cf46a7dc7eb63.png
[73818f1984922e768818a2fd786f68f3.png]: /images/20221022/e84196dc012d4c8f93cf98b90fafe334.png