118. 二叉树的锯齿形层序遍历

这是我的代码(它是不正确的,对的请看力扣,我这里只是记录一个有趣的函数)

import math


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

    def __str__(self):
        return self.val


root = TreeNode(3)
t1 = TreeNode(9)
t2 = TreeNode(20)
t3 = TreeNode(None)
t4 = TreeNode(None)
t5 = TreeNode(15)
t6 = TreeNode(7)

t1.left = t3
t1.right = t4

t2.left = t5
t2.right = t6

root.left = t1
root.right = t2


class Solution(object):
    def zigzagLevelOrder(self, root):
        # 在写这个的时候我以为root是满二叉树,也就是说没有地方用None补齐
        node_list = self.ground(root)  # 这个函数是一个广度遍历二叉树的函数

        lenght = len(node_list) + 1  # 满二叉树的节点等于2^n -1 ,其中n是二叉树的层数
        cengji = int(math.log(lenght, 2))   # 这个是我用对数函数求出来的二叉树层数
        k = 0  # 其中k表示每次取截取node_list的起始位置
        ret_list = []
        for i in range(1, cengji + 1):  
            num = 2 ** (i-1)   # 计算一层有几个节点
            cut_list = node_list[k: num + k]  # num + k是截取的最后位置
            if i % 2:
                cut_list = cut_list
            else:
                cut_list = cut_list[::-1]

            cut_list = [item for item in cut_list if item]

            ret_list.append(cut_list)
            k += num
        return ret_list

    def ground(self, root):
        if not root:
            return
        retList = []
        queue = []
        queue.append(root)
        while queue:
            r = queue.pop(0)
            retList.append(r.val)
            if r.left:
                queue.append(r.left)

            if r.right:
                queue.append(r.right)

        return retList


s1 = Solution()
print(s1.zigzagLevelOrder(root))

118. 二叉树的锯齿形层序遍历

原文：https://www.cnblogs.com/liuzhanghao/p/14174494.html