本文共 2657 字，大约阅读时间需要 8 分钟。

leetcode中，二叉树也是一块重点，对于树结构衍生出的问题，一般用递归的方法会比较多。

如上图的二叉树： 中序遍历：左-根-右的顺序，结果是[4,2,5,1,6,3] 每层遍历：从最上面那层往下面读，结果是[1,2,3,4,5,6] Z字形遍历：和每层遍历差不多，只是走Z字，结果是[1,3,2,4,5,6]

二叉树的中序遍历

对于二叉树的中序遍历，就是左-根-右这种遍历顺序。

有递归和迭代写法：非递归就用栈来实现

res, stack = [], []        while True:            while root:                stack.append(root)                root = root.left            if not stack:                return res            node = stack.pop()            res.append(node.val)            root = node.right

我们看栈的情况，while true保证了直到栈为空（if not stack）的时候我们结束循环，这时候我们已遍历栈中所有所有元素。

while root让我们一直会保证左边的元素会先进栈，直到左边没有元素为止，.pop()弹出后入栈的，后入栈的是最底层的左侧元素。 比如第一次while true循环，1，2，4先进stack栈，4的左边没有元素，所以把4先出栈到res里，再将root更新成4的右孩子，现在stack: [1,2], res: [4] 第二次while true循环，4的右孩子不存在，会执行2出栈，将root更新成2的右孩子，现在stack: [1], res: [4,2] 第三次 while true循环, 5进stack栈，5的左边没有元素，5出栈到res里，将root更新成5的右孩子，stack: [1], res:[4,2,5] … 这个的思想就是，while root和root=root.left保证了左子树的元素纷纷统统入栈，当我们要考虑一个元素的右孩子时，就说明这个元素已经被我们出栈了。一个元素的右孩子也为空就说明我们已经走到了最左侧，应该往上一层考虑了。这里的root = node.right很巧妙（下一次循环与这一次计算结果有关，迭代）。

递归写法：

def inorderTraversal1(self, root):    res = []    self.helper(root, res)    return res    def helper(self, root, res):    if root:        self.helper(root.left, res)        res.append(root.val)        self.helper(root.right, res)

这个还是挺直观的，按左-根右的顺序调用函数helper()，函数调用栈会是helper(1.left), append(1), helper(1.right),再对helper（1.left）的函数调用栈进行分析，总是左-根-右的顺序。

每层遍历

要求输出的是一个二维列表，每个元素是每层元素所组成的列表。

比如示例就应该输出[[1],[2,3],[4,5,6]]

def levelOrder(self, root):    if not root:        return []    ans, level = [], [root]    while level:        ans.append([node.val for node in level])        temp = []        for node in level:            temp.extend([node.left, node.right])        level = [leaf for leaf in temp if leaf]  #只把非None的孩子添加进去    return ans

思想就是开枝散叶的思想，有两个列表很关键，一个是结果列表res存我们的结果，一个是每层元素列表level存每层的树结点元素。只要这层不是空的，我就把这层元素添加进ans里，再用extend方法将孩子列表做好（对每个本层元素都开枝散叶它下层元素），并更新层元素列表。

Z字形遍历

要求输出的是一个二维列表，每个元素是每层元素所组成的列表。

比如示例就应该输出[[1],[3,2],[4,5,6]]

思想和上述一样，就是加个flag对第偶数次遍历反序

def zigzagLevelOrder(self, root):        """        :type root: TreeNode        :rtype: List[List[int]]        """        if not root:            return []        ans, level = [], [root]        flag = 1        while level:            ans.append([node.val for node in level][::flag]) #偶数次反序            temp = []            for node in level:                temp.extend([node.left, node.right])            level = [leaf for leaf in temp if leaf]  #只把非None的孩子添加进去            flag *= -1        return ans

总结一下：

1.对于树的中序遍历，递归好写很多，迭代不太直观 2.对于树的每层遍历，extend一次加多个元素，level = [leaf for leaf in temp if leaf] 这个写的不错 3.在Z字形遍历中，flag的妙用，我一开始想的话就会用counter，循环一次加1，如果偶数次就逆向输出，代码太不简洁了。

转载地址：http://nkksi.baihongyu.com/