[人工智能]LC543.二叉树的直径

题目

查看题目

思路

对二叉树的理解还是差点意思啊。

• 最初的思想：将左子树的深度和右子树的深度加起来即可。但是这里题目提示可能不经过根节点，所以要考虑这种特殊情况，即下图这种情况：

很明显任意两节点最长的是[6,4,2,5,3]而不是简单的经过根节点的左右节点的深度之和。

• 为了达到找到最长距离的要求，定义一个全局变量，用来存储当前最长的路径长度。递归中，比较左右子树的和与当前最长的路径进行比较，用来更新当前最长的路径长度。
• return Math.max(left,right)+1;// 返回该节点为根的子树的深度 这一语句的中的+1是当遍历到叶子节点时，因为叶子节点没有左子树和右子树，所以返回当前深度（叶子节点本身就是一层，所以要加1）然后后面时用递归进行实现。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int raw=0;
    public int diameterOfBinaryTree(TreeNode root) {
        func(root);
        return raw;
    }

    public  int func(TreeNode root){
         if(root==null) return 0;// 访问到空节点了，返回0
        int left=func(root.left);// 左儿子为根的子树的深度
        int right=func(root.right);// 右儿子为根的子树的深度
        raw=Math.max(raw,left+right);// 计算d_node即L+R+1 并更新raw
        return Math.max(left,right)+1;// 返回该节点为根的子树的深度


    }
}