【剑指offer】JZ55 二叉树的深度 python

【剑指offer】JZ55 二叉树的深度 python

【剑指offer】JZ55 二叉树的深度

题目

1、层次遍历

class TreeNode:
    def __init__(self, data=0):
        self.val = data
        self.left = None
        self.right = None


class Solution:
    def TreeDepth(self , pRoot: TreeNode) -> int:
        # write code here
        if pRoot is None:
            return 0
        count = 0
        now_layer = [pRoot]
        next_layer = []
        while now_layer:
            for i in now_layer:
                if i.left:
                    next_layer.append(i.left)
                if i.right:
                    next_layer.append(i.right)
            count += 1
            now_layer, next_layer, = next_layer, []
        return count

if __name__ == '__main__':
    inp = [1,2,3,4,5,'#',6,'#','#',7]
    bt = TreeNode(1)

    bt.left = TreeNode(2)
    bt.right = TreeNode(3)

    bt.left.left = TreeNode(4)
    bt.left.right = TreeNode(5)
    bt.right.left = None
    bt.right.right = TreeNode(6)

    bt.left.left.left = None
    bt.left.left.right = None
    bt.left.right.left = TreeNode(7)

    solution = Solution()
    print('深度：', solution.TreeDepth(bt))

深度： 4

2、递归

class TreeNode:
    def __init__(self, data=0):
        self.val = data
        self.left = None
        self.right = None

class Solution:
    def TreeDepth(self , pRoot: TreeNode) -> int:
        # write code here
        if not pRoot:
            return 0
        left = right =0
        if pRoot.left:
            left = self.TreeDepth(pRoot.left)
        if pRoot.right:
            right = self.TreeDepth(pRoot.right)
        return max([left,right])+1

if __name__ == '__main__':
    inp = [1,2,3,4,5,'#',6,'#','#',7]
    bt = TreeNode(1)

    bt.left = TreeNode(2)
    bt.right = TreeNode(3)

    bt.left.left = TreeNode(4)
    bt.left.right = TreeNode(5)
    bt.right.left = None
    bt.right.right = TreeNode(6)

    bt.left.left.left = None
    bt.left.left.right = None
    bt.left.right.left = TreeNode(7)

    solution = Solution()
    print('深度：', solution.TreeDepth(bt))

深度： 4