543.E 二叉树的直径

Problem: 543. 二叉树的直径

思路

思路1：递归。helper方法返回两个字段，字段1是最长路径的节点个数，字段2是树的深度。

思路2：主要是代码写法的差异，用一个变量来维护全局的最长路径节点数量，代码相对好理解一些。

Code

代码1：

func diameterOfBinaryTreeV1(root *TreeNode) int {
	path, _ := helper(root)
	return path - 1
}

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

	lpath, ldepth := helper(root.Left)
	rpath, rdepth := helper(root.Right)
	return max(max(lpath, rpath), ldepth+rdepth+1), max(ldepth, rdepth) + 1
}

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

代码2：

func diameterOfBinaryTree(root *TreeNode) int {
	ans := 0
	depth(root, &ans)
	return ans - 1
}

func depth(root *TreeNode, ans *int) int {
	if root == nil {
		return 0
	}

	l := depth(root.Left, ans)
	r := depth(root.Right, ans)
	*ans = max(*ans, l+r+1)
	return max(l, r) + 1
}