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

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

二叉树的前序遍历

题目描述 :

给定一个二叉树，返回它的 前序 遍历。

示例:

输入: [1,null,2,3]
1
\
2
/
3

输出: [1,2,3]

来源：力扣（LeetCode）
OJ链接

相关:
二叉树的中序遍历(非递归)
二叉树的后序遍历(非递归)
二叉树的层序遍历(非递归)

分析:

非递归前序遍历只需要将右孩子入栈, 遍历根节点和左孩子, 再将右孩子出栈, 从而实现 根->左->右的前序遍历, 上代码:

  1. class Solution {
  2.      vector<int> res;
  3. public:
  4.     vector<int> preorderTraversal(TreeNode* root) {
  5.        stack<TreeNode*> s;
  6.        do{
  7.            if (!s.empty()) {
  8.                root = s.top();
  9.                s.pop();
  10.            }
  11.            while(root) {
  12.                res.push_back(root->val);
  13.                if (root->right) s.push(root->right);
  14.                root = root->left;
  15.            }
  16.        } while (!s.empty());
  17.        return res;
  18.     }
  19. };

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70

发表评论

表情：
评论列表 （有 0 条评论，111人围观）

还没有评论，来说两句吧...

相关阅读

    相关 二叉树的前序遍历的非递归实现

    我们知道二叉树的遍历主要有，前序，中序，后续，我们常用递归的方式进行实现，而我们都知道能用递归函数实现，都可以用数据结构栈进行实现。 下面我们就用栈的数据结构来处理二叉树的前

    冷不防冷不防/ 0 赞/ 84 阅读