p65 二叉树的直径 (leetcode 543)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了p65 二叉树的直径 (leetcode 543)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2531字，纯文字阅读大概需要4分钟。
内容图文
一：解题思路
分析：这个题目的本质其实就是要求最长路径，当最长路径求出来了，二叉树的直径就知道了。如果所要求的最长路径要经过根节点，那么我们可以递归的去求各个子树的最长路径。但是最长路径并不一定包含根节点，所以，我们可以把所有的路径给穷举出来，然后进行比较得出最大值就行。如果采用自顶向下的方式来求解的话，那么就会有很多的重复计算在里面。时间复杂度为：Time：O(n^2),所以我们将采用自底向上的思路来进行计算。底层的计算结果可以留给上层来使用，这样，Time:O(n),Space:O(n)
方法一(递归)：Time:O(n),Space:O(n)
方法二(迭代)：Time:O(n),Space:O(n)
二：完整代码示例 (C++版和Java版)
方法一C++：
class
Solution {
public
:
int max(int a, int b) { return a > b ? a : b;}
int maxDepth(TreeNode* root, vector<int>& d)
{
if (root == NULL) return0;
int left = maxDepth(root->left,d);
int right = maxDepth(root->right,d);
d[0] = max(d[0],left+right);
return max(left,right)+1;
}
int diameterOfBinaryTree(TreeNode* root)
{
vector<int> d(1,0);
maxDepth(root,d);
return d[0];
}
};
方法一Java：
class
Solution {
private
int maxDepth(TreeNode root,int[] d)
{
if(root==null) return0;
int left=maxDepth(root.left,d);
int right=maxDepth(root.right,d);
d[0]=Math.max(d[0],(left+right));
return Math.max(left,right)+1;
}
publicint diameterOfBinaryTree(TreeNode root)
{
int[] d=newint[1];
maxDepth(root,d);
return d[0];
}
}
方法二C++：
class
Solution {
public
:
int max(int a, int b) { return a > b ? a : b;}
int diameterOfBinaryTree(TreeNode* root)
{
if (root == NULL) return0;
int diameter = 0;
map<TreeNode*, int> depthMap;
stack<TreeNode*> st;
st.push(root);
while (!st.empty())
{
TreeNode* node = st.top();
if (node->left != NULL && depthMap.count(node->left) == 0)
{
st.push(node->left);
}
elseif (node->right != NULL && depthMap.count(node->right) == 0)
{
st.push(node->right);
}
else
{
st.pop();
int left = depthMap[node->left];
int right = depthMap[node->right];
diameter = max(diameter,left+right);
depthMap[node] = max(left, right) + 1;
}
}
return diameter;
}
};
方法二Java:
class
Solution {
public
int
diameterOfBinaryTree(TreeNode root)
{
if(root==null) return0;
int diameter=0;
Map<TreeNode,Integer> depthMap=new HashMap<>();
Stack<TreeNode> st=new Stack<>();
st.push(root);
while(!st.empty())
{
TreeNode node=st.peek();
if(node.left!=null && !depthMap.containsKey(node.left))
{
st.push(node.left);
}
elseif(node.right!=null && !depthMap.containsKey(node.right))
{
st.push(node.right);
}
else
{
st.pop();
int left=depthMap.getOrDefault(node.left,0);
int right=depthMap.getOrDefault(node.right,0);
diameter=Math.max(diameter,(left+right));
depthMap.put(node,Math.max(left,right)+1);
}
}
return diameter;
}
}
原文：https://www.cnblogs.com/repinkply/p/12527305.html
内容总结
以上是互联网集市为您收集整理的p65 二叉树的直径 (leetcode 543)全部内容，希望文章能够帮你解决p65 二叉树的直径 (leetcode 543)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。