Leetcode-543-二叉树的最大直径

Leecode-543-Diameter of Binary Tree

思路：深度优先搜索

说在前面

说在前面：看本题之前，先去把Leetcode-104-二叉树的最大深度 做一下，效果会更好。（这两题有异曲同工之妙）。

题目描述

给定如下一个二叉树

    1
   / \
  2   3
 / \     
4   5

求任意两个节点之间距离的最大值（可能不经过根节点）

Solution：DFS

• 思路：首先我们知道一条路径长度是该路径经过的节点数量减一，所以求直径等效于（求路径经过节点的最大值 ）。

• 其中任意一条路径均可以被看做由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到的。（如下图所示）

从上图可以看出：

• 路径[9,4,2,5,7,8] 可以看作2为起点，从其左儿子向下遍历的路径[2,4,9]和其右儿子[2,5,7,8] 拼接得到。

• 对于该节点的左儿子向下遍历经过最多的节点数 L（即以左儿子为根的子树的深度），其右儿子向下遍历经过最多的节点数 R （即以右儿子为根的子树的深度）。那么以该节点为起点的路径经过的节点数的最大值为L+R+1

Java

Solution :

1. 定义一个递归函数 depth(node) 来计算d_node的值，函数返回该节点为根的子树的深度。
2. 那么以节点为根的子树深度就是 max(L,R) + 1
3. 那么该节点的d_node的值就是 L + R + 1

class Solution{
    // 全局变量
    int ans;

    public int diameterOfBinaryTree(TreeNode root){
        ans = 1;
        depth(root);
        // 结果是最大节点数-1 （也就是路径直径）
        return ans - 1;
    }


    // 返回最大节点数
    public int depth(TreeNode node){
        // 访问到空节点了，返回0
        if (node == null){
            return 0;
        }

        // 左儿子为根的子树的深度
        int L = depth(node.left);
        // 右儿子为根的子树的深度
        int R = depth(node.right);

        // 计算d_node即L+R+1 并更新ans
        ans = Math.max(ans,L + R + 1);
        // 返回该节点为根的子树的深度
        return Math.max(L,R) + 1;
    }
}

• 时间复杂度: O（n) 。其中n是二叉树的节点数，即遍历一棵二叉树的时间复杂度，每个节点只访问一次。
• 空间复杂度：O(height)。其中height是二叉树的高度。由于递归过程中每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，而递归的深度就是二叉树的高度，并且每次递归调用只使用了常数个变量(即ans)。

Python

Solution :

打赏