开篇记录面试第21天-二叉树遍历

直到今天，我觉得自己有点坚持不住了，开始疯狂地买东西，给家里人打电话，找人聊天，内心积郁的压力已经在慢慢地吞噬我了，不知道还能坚持多久，也不知道将来能迎来一份什么样的工作。加油吧。

今天看了几个算法学习的视频，收获最大的是解决了昨天的蛇形遍历二叉树（LeetCode上叫锯齿形）。
问题是这样的：给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。给定二叉树 [3,9,20,null,null,15,7]，输出[
[3],
[20,9],
[15,7]
]。
解题思路：这个问题里有两个关键，一个是在哪里换行，一个是换行后输出顺序。我在网上学习到的思路是，用list模拟一个队列，先把root节点放进队列，然后把它的左右子孩子分别放入队列，这时弹出root节点，输出root。第二次的时候，把root左孩子的孩子节点放入队列，弹出root的左孩子，同时把root的右孩子的孩子放入队列，弹出root右孩子，在这一层，弹出的两个节点按弹出顺序反向遍历，这里用一个flag变量来控制，每执行一次循环，flag*-1，就可以实现每层变换顺序了。
代码:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
            if root is None:
                return []
            res = []
            node = []
            node.append(root)
            flag = 1
            while len(node) is not 0:
                row = []
                for i in range(len(node)):
                    if node[0].left:
                        node.append(node[0].left)
                    if node[0].right:
                        node.append(node[0].right)
                    row.append(node.pop(0).val)
                row = row[::flag]
                res += [row]
                flag *= -1
            return res

这样的话其实顺便就把二叉树的顺序遍历，逆序遍历一起都会了。
说真的，要看会一个算法，还真的挺费精力的。希望能在我崩溃之前，把该看会的知识点赶紧看会吧！！加油加油！