剑指offer面试题55：二叉树的深度（golang实现）

题目描述

该类题目书中共有两题，以下为题目描述：

算法分析

求二叉树的深度一般采用递归实现

1. 第一题直接要求二叉树的深度，易知二叉树的深度等于左子树的深度和右子树的深度的最大值加一（加上根节点）即 depth(root) = max(depth(root.Left), (root.Right)) + 1，递归求解即可。
2. 第二题要求判断一棵二叉树是不是二叉平衡树，相比第一题，第二题如果直接递归求解的话，会递归计算每一个节点的深度。所以为了使每个节点只被调用一次，可以使用后序遍历二叉树（即左右中的顺序），每遍历到一个节点时，它的左右子树都已经遍历完毕。

复杂度分析

问题规模为二叉树的节点个数n，对于两道题：

• 时间复杂度：O(n)，最坏情况下二叉树会退化为链表，递归深度为n
• 空间复杂度：O(n)，最坏情况下递归深度为n，每次递归空间消耗为常数级。

Golang代码如下

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func maxDepth(node *tree.BinaryTreeNode) int {
	if node == nil {
		return 0
	}
	return max(maxDepth(node.Left), maxDepth(node.Right)) + 1
}

func getDepth(node *tree.BinaryTreeNode) int {
	if node == nil {
		return 0
	}
	leftDepth := getDepth(node.Left)
	rightDepth := getDepth(node.Right)
	abs := func(num int) int {
		if num < 0 {
			return -num
		}
		return num
	}
	if leftDepth == -1 || rightDepth == -1 || abs(leftDepth - rightDepth) > 1 {
		return -1
	}
	if leftDepth > rightDepth {
		return leftDepth + 1
	}
	return rightDepth + 1
}

func isBalanced(root *tree.BinaryTreeNode) bool {
	return getDepth(root) != -1
}