西安市城乡建设管理局网站的公示栏,微信外部链接网站,品牌网站设计服务,如何在网站做宣传Problem: 543. 二叉树的直径 文章目录 题目描述思路解题方法复杂度Code 题目描述 给你一棵二叉树的根节点#xff0c;返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们… Problem: 543. 二叉树的直径 文章目录 题目描述思路解题方法复杂度Code 题目描述 给你一棵二叉树的根节点返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。 思路
本题目要求我们求取二叉树中最长的路径可将其按递归的思想分解成的最小子问题如下 1.求取左子树的最长路径 2.求取右子树的最长路径 3.合并求取树的最长路径 解题方法 1.定义成员变量result记录最长“直径” 2.编写递归代码依次得到左右子树的最长“直径” 3.将左右子树的最长“直径”合并得到当前的最长“直径”并与result比较更新 4.在归的过程中返回当前左右子树的最长路径加一因为此时要回退到上一个节点所以要加一!!! 复杂度
时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( h ) O(h) O(h) h h h为树的高度 Code
/*** 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 {//Recode the longest diameterprivate int result 0;/*** Gets the path length between any two nodes of a tree** param root The root node of a tree* return int*/public int diameterOfBinaryTree(TreeNode root) {claMaxHeight(root);return result;}/*** Recursively gets the longest path containing the root node** param root The root node of a tree* return int*/public int claMaxHeight(TreeNode root) {if (root null) {return 0;}//Gets the longest path of the left and right subtreeint maxLeftHeight claMaxHeight(root.left);int maxRightHeight claMaxHeight(root.right);//Get the longest path(diameter)int diameter maxLeftHeight maxRightHeight;//Update the longest path(diameter)if (diameter result) {result diameter;}return Math.max(maxLeftHeight, maxRightHeight) 1;}
}
