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 diameter
private 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 subtree
int 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;
}
}
参考文章
发表评论