LeetCode[144] 二叉树的前序遍历（迭代）

淩亂°似流年 2022-11-20 08:19 215阅读 0赞

> 前言：今天的 LeetCode 上的每日一题，[二叉树的前序遍历][Link 1]，用 C++ 实现

## 题目描述 ##

给定一个二叉树，返回它的前序遍历。  
![示例][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9tYV8yMDE4_size_16_color_FFFFFF_t_70_pic_center]

## 算法分析 ##

1.  二叉树的递归前序遍历，先访问根节点，再访问左子树，最后访问右子树
2.  迭代算法，利用栈保存节点信息，完成遍历操作

## 代码实现 ##

递归代码：

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

![2][]  
迭代代码：注意入栈顺序，左子树先出栈，因此右子树先入栈

class Solution {
        
    public:
        vector<int> preorderTraversal(TreeNode* root) {
        
            vector<int> result;
            if(root == NULL) {
        
                return result;
            }
            stack<TreeNode*> Nodes;
            Nodes.push(root);
            TreeNode* cur = NULL;
            while(!Nodes.empty()) {
        
                cur = Nodes.top();
                result.push_back(cur -> val);
                Nodes.pop();
                if(cur -> right) {
        
                    Nodes.push(cur -> right);
                }
                if(cur -> left) {
        
                    Nodes.push(cur -> left);
                }
            }
            return result;
        }
    };

![1][]

[Link 1]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9tYV8yMDE4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/113377fa88154008a8c398e4e8e894d9.png
[2]: /images/20221120/27a08a1d1493436f964141829863cf11.png
[1]: /images/20221120/be1da436776141ad908a38d5f41d5948.png