144. Binary Tree Preorder Traversal

 

Given a binary tree, return the  preorder  traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

 

一般我们提到 树的遍历,最常见的有先序遍历,中序遍历,后序遍历和层序遍历,它们用递归实现起来都非常的简单。而题目的要求是不能使用递归求解,于是只能考虑到用非递归的方法,这就要用到stack来辅助运算。由于先序遍历的顺序是”根-左-右”, 算法为:

1. 把根节点 push 到栈中

2. 循环检测栈是否为空,若不空,则取出栈顶元素,保存其值,然后看其右子节点是否存在,若存在则 push 到栈中。再看其左子节点,若存在,则 push 到栈中。

参见代码如下:

 

解法一:

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

 

下面这种写法使用了一个辅助结点p,这种写法其实可以看作是一个模版,对应的还有中序和后序的模版写法,形式很统一,方便于记忆。辅助结点p初始化为根结点,while 循环的条件是栈不为空或者辅助结点p不为空,在循环中首先判断如果辅助结点p存在,那么先将p加入栈中,然后将p的结点值加入结果 res 中,此时p指向其左子结点。否则如果p不存在的话,表明没有左子结点,取出栈顶结点,将p指向栈顶结点的右子结点,参见代码如下:

 

解法二:

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

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/144

 

类似题目:

Binary Tree Inorder Traversal

Binary Tree Postorder Traversal

Binary Tree Level Order Traversal

Verify Preorder Sequence in Binary Search Tree

Verify Preorder Serialization of a Binary Tree

 

参考资料:

https://leetcode.com/problems/binary-tree-preorder-traversal/

https://leetcode.com/problems/binary-tree-preorder-traversal/discuss/45468/3-Different-Solutions

https://leetcode.com/problems/binary-tree-preorder-traversal/discuss/45493/Accepted-code.-Explaination-with-Algo.

https://leetcode.com/problems/binary-tree-preorder-traversal/discuss/45266/Accepted-iterative-solution-in-Java-using-stack.

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation