一、二叉树的深度
题目:
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树[3,9,20,null,null,15,7]
, 3 / \ 9 20 / \ 15 7
返回它的最大深度 3 。
思路1:递归
边界:一旦root == None则返回深度为0。否则进入递归子问题。
递归子问题:max(左树深度,右树深度)+ 1
def dfs(root): #边界 if not root: return 0 #递归子问题 else: left = dfs(root.left) right = dfs(root.right) return max(left,right)+1class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = Noneroot = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.left.right = TreeNode(5)height = dfs(root)
思路2:深度遍历dfs
边界:一旦root == None则记录深度大小tmp,判断是否大于res(结果)。否则进入递归子问题。
递归子问题:将当前深度tmp + 1,传入左子树和右子树。
代码:
#全局变量res = 0def dfs(root,tmp): global res ##边界 if not root: res = max(res,tmp) return ###递归子问题 else: dfs(root.left,tmp+1) dfs(root.right,tmp+1)class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = Noneroot = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.left.right = TreeNode(5)dfs(root,0)print(res)
二、