一：解题思路
分析：这个题目的本质其实就是要求最长路径，当最长路径求出来了，二叉树的直径就知道了。如果所要求的最长路径要经过根节点，那么我们可以递归的去求各个子树的最长路径。但是最长路径并不一定包含根节点，所以，我们可以把所有的路径给穷举出来，然后进行比较得出最大值就行。如果采用自顶向下的方式来求解的话，那么就会有很多的重复计算在里面。时间复杂度为：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) return 0; 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) return 0; 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; } public int diameterOfBinaryTree(TreeNode root) { int[] d=new int[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) return 0; 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); } else if (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) return 0; 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); } else if(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