一、二叉树的深度

题目：

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,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)+1

class TreeNode(object):

    def __init__(self, x):

        self.val = x

        self.left = None

        self.right = None

root = 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 = 0

def 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 = None

root = 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)

二、

巴特西

深度遍历DFS---树

一、二叉树的深度

题目：

思路1：递归

思路2：深度遍历dfs

代码：

最新文章

热门文章