首页 > itarticle > l104 maximum depth of binary tree

l104 maximum depth of binary tree

admin 11月 13, 2020 0

题目描述

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path 
from the root node down to the farthest leaf node.

解题思路

将maxDepth设置为0，判断当面节点的depth是否大于maxDepth，如果是就替换。

Go实现

func (root *TreeNode, depth *int, level int){
    if root == nil{
        if *depth < level{
            *depth = level
        }
        return
    }else{
        travel(root.Left, depth, level+1)
        travel(root.Right, depth, level+1)
    }
}

func maxDepth(root *TreeNode) int {
    var depth int
    travel(root, &depth, 0)
    return depth
}

这个方法遍历了两边，是否可以减少遍历

func maxDepth(root *TreeNode) int {
    if root == nil{
        return 0
    }

    leftDepth  := maxDepth(root.Left)
    rightDepth := maxDepth(root.Right)

    if leftDepth >rightDepth{
        return leftDepth+1
    }else {
        return rightDepth+1
    }
}