二叉树的前序遍历(非递归)

Bertha 。 2023-05-31 07:24 41阅读 0赞

**二叉树的前序遍历**

> **题目描述 :**
> 
> 给定一个二叉树，返回它的 前序 遍历。
> 
>  示例:
> 
> 输入: \[1,null,2,3\]    
>    1  
>     \\  
>      2  
>     /  
>    3 
> 
> 输出: \[1,2,3\]
> 
> 来源：力扣（LeetCode）  
> **[OJ链接][OJ]**
> 
> **相关:**  
> [二叉树的中序遍历(非递归)][Link 1]  
> [二叉树的后序遍历(非递归)][Link 2]  
> [二叉树的层序遍历(非递归)][Link 3]
> 
> **分析: **
> 
> 非递归前序遍历只需要将右孩子入栈, 遍历根节点和左孩子, 再将右孩子出栈, 从而实现 根->左->右的前序遍历, 上代码:

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70][]

[OJ]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal
[Link 1]: https://blog.csdn.net/qq_41071068/article/details/102711009
[Link 2]: https://blog.csdn.net/qq_41071068/article/details/102711278
[Link 3]: https://blog.csdn.net/qq_41071068/article/details/102711504
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70]: /images/20230531/53523f3cb02a4b7aa9333e7d53f47bc3.png