常州网站推广软件厂家,网址收录入口,如何给自己网站做网站优化,企业管理系统排名543. 二叉树的直径
简单题#xff0c;确实不难。 相当于就是求节点的深度。左孩子的最大深度 右孩子的最大深度 1 根节点深度。 本题要求的就是路径数#xff0c;这里的路径数 节点数 - 1#xff0c;然后想一下#xff0c;对于一个节点来说#xff0c;以他为根左右两…543. 二叉树的直径
简单题确实不难。 相当于就是求节点的深度。左孩子的最大深度 右孩子的最大深度 1 根节点深度。 本题要求的就是路径数这里的路径数 节点数 - 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 max 0;public int diameterOfBinaryTree(TreeNode root) {depth(root);return max;}public int depth(TreeNode root){if(root null) return 0;int left depth(root.left);int right depth(root.right);if(max left right) //这里这个max就是不加上根节点的节点个数也等于路径个数。max left right;return Math.max(left, right) 1;}
}
