必会高频算法

二叉树遍历二叉树遍历系列总结

原文地址：链接地址

这里分别给出了三种二叉树的遍历方法与N叉树的前序遍历，及其时空复杂度
1：递归：直接递归版本、针对不同题目通用递归版本（包括前序、中序、后序）
2：迭代：最常用版本（常用主要包括前序和层序，即【DFS和BFS】）、【前中后】序遍历通用版本（一个栈的空间）、【前中后层】序通用版本（双倍栈（队列）的空间）
3：莫里斯遍历：利用线索二叉树的特性进行遍历
4：N叉树的前序遍历

LeeCode题目链接：
144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
102. 二叉树的层序遍历
589. N叉树的前序遍历

主要参考资料：
LeetCode官方题解
powcai的题解
Grandyang的博客
Annie Kim’s Blog
维基百科对于线索二叉树的解释
莫里斯的文章

144. 二叉树的前序遍历

注意点：元素弹栈顺序为最终元素顺序，因此入栈时需要和遍历顺序相反

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        stack, result = [root], []
        while stack:
            item = stack.pop()
            result.append(item.val)
            # 入栈先右后左，保证出栈时的顺序为先左后右
            if item.right:
                stack.append(item.right)
            if item.left:
                stack.append(item.left)
        return result