leetcode-leetcode-543-Diameter-of-Binary-Tree

描述

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

分析

这题跟 563 几乎一毛一样。要求的是二叉树中任意两个节点间最长的路径长度。注意这里的任意两个节点，可以通过根节点，也可以不通过根节点。

这道题的重点其实是要找到一个节点，这个节点的左子树深度和右子树深度之和是所有节点中最大的，而要计算一个节点的深度，可以采用递归的方式，比较左子树和右子树的深度，取较大的那个加1。如果该节点为 null，则返回0。

解决方案1(Javascript)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */

let result
var diameterOfBinaryTree = function(root) {
    result = 1;
    postOrder(root);
    return result-1;
};

var postOrder = function(root) {
    if (root == undefined) {
        return 0;
    }
    let l = postOrder(root.left);
    let r = postOrder(root.right);
    result = Math.max(result, l+r+1);
    return Math.max(l, r) + 1;
}

解决方案2（Golang）

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func diameterOfBinaryTree(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    length := depth(root.Left) + depth(root.Right)
    return int(math.Max(float64(length), math.Max(float64(diameterOfBinaryTree(root.Left)), float64(diameterOfBinaryTree(root.Right)))))
}

func depth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return int(math.Max(float64(depth(root.Left)), float64(depth(root.Right)))) + 1
}/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func diameterOfBinaryTree(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    length := depth(root.Left) + depth(root.Right)
    return int(math.Max(float64(length), math.Max(float64(diameterOfBinaryTree(root.Left)), float64(diameterOfBinaryTree(root.Right)))))
}

func depth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return int(math.Max(float64(depth(root.Left)), float64(depth(root.Right)))) + 1
}

描述

分析

解决方案1(Javascript)

解决方案2（Golang）

题目来源