L104 Maximum Depth of Binary Tree

发表于 | 阅读次数

题目描述

1
2
3
4
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实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func travel(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
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
    }
}