二叉树层次遍历c语言_LeetCode103-二叉树的锯齿形层次遍历

这两天一只小黑猫一直跑到我们实验室窗户外面趴着

可能是前两天给它喂了些吃的

现在已经赖着不走了

饿了就朝我们叫

饱了就蜷缩在角落里晒太阳

真的是快活了！

103-二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：

给定二叉树

[3,9,20,null,null,15,7]

,

3
   / 
  9  20
    /  
   15   7
           

返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]
           

思路：

这一题其实和第102题很类似了，对第102题-二叉树的层次遍历不熟悉的朋友，可以先看看这道题。

程小新同学：LeetCode102-二叉树的层次遍历​zhuanlan.zhihu.com

第102题是正常的层次遍历，而这一题无非是在每一层遍历时玩了些花样。你可以这样理解：

单数层时从左到右遍历取数，偶数层时从右到左逆序遍历取数

。我其实就是在第102题层次遍历的代码中加了一个is_reverse标记，用来帮助我们在单层遍历时是否需要逆序。是不是很easy，废话不多说，直接上代码吧！

代码如下：

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        # 用来保存锯齿形层次遍历二叉树的结果
        root_list = []
        if root:
            # 用来保存每一层节点
            node_list = [root]
            # 判断是否逆序遍历的标志
            is_reverse = False
            while node_list:               
                # 用来保存每一层节点对应的val值
                level_data = []
                # 用来暂时保存下一层节点
                next_nodes = []
                for node in node_list:
                    level_data.append(node.val)
                    if node.left and node.left.val is not None:
                        next_nodes.append(node.left)
                    if node.right and node.right.val is not None:
                        next_nodes.append(node.right)
                if is_reverse is True:
                    level_data.reverse()
                is_reverse = not is_reverse
                root_list.append(level_data)
                node_list = next_nodes
        return root_list

    def createBTree(self, data, index=0):
        pNode = None
        if index < len(data):
            pNode = TreeNode(data[index])
            pNode.left = self.createBTree(data, 2*index+1)
            pNode.right = self.createBTree(data, 2*index+2)
        return pNode


if __name__ == "__main__":
    data = [3, 9, 20, None, None, 15, 7]
    root = Solution().createBTree(data)
    root_list = Solution().zigzagLevelOrder(root)
    print(root_list)
           

执行效率也是非常不错，达到了100%！