力扣543. 二叉树的直径
力扣543. 二叉树的直径
这题其实并不难，力扣分类为简单题，但是我二叉树的题做得并不多，并且对其一些经典算法算不上熟悉。在这里记录一下。
下面我们先看一下原题：
我最初的想法比较简单，使用的是广度优先搜索，直接搜索root左右树的最大深度，然后直接相加，代码如下：
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
int left=0,right=0;
TreeNode l = root.left,r = root.right;
if(l==null&&r==null){
return 0;
}
ArrayDeque<TreeNode> first = new ArrayDeque<>();
ArrayDeque<TreeNode> second = new ArrayDeque<>();
if (l!=null) {
first.addLast(l);
left=diameterOfBinaryTreeBfs(first,second);
}
if (r!=null) {
first.addLast(r);
right=diameterOfBinaryTreeBfs(second,first);
}
return left+right-1;
}
public int diameterOfBinaryTreeBfs(ArrayDeque<TreeNode> first,ArrayDeque<TreeNode> second) {
int num=1;
while (!first.isEmpty()){
while (!first.isEmpty()) {
TreeNode node = first.removeFirst();
if (node.left!=null){
second.addLast(node.left);
}
if (node.right!=null){
second.addLast(node.right);
}
}
ArrayDeque<TreeNode> temp=second;
second=first;
first=temp;
num++;
}
return num;
}
}
但是我提交后发现有一个用例过不去。我又仔细看了一下题目，有说，不一定会经过root节点，这下我就有点懵逼了，如果我还是使用我的算法，那就得暴力遍历节点，时间复杂度会变为O(n2)，这显然，不用提交我都知道跨度过不了，但是我想了一会儿确实没有更好的想法，于是我看了一下官方解答，发现官方解答的思路是使用深度优先搜索，递归的方式来计算每个节点的深度，同时在计算深度的过程中更新最大直径。其实说白了，就是做了一次深度优先搜索，同时在过程中顺便记录了一下左右子树的深度。我们将最大路径当作一个子树提出来，会发现这个路径等于左子树的深度加上右子树的深度。
那么我们遍历的时候顺便记录一下就可以了，但是这个操作会记录下所有的路径长度，但是没关系，我们取最大的就行。下面是我根据这个思路自己实现的代码：
class Solution {
int res=1;//只记录最长路径
public int diameterOfBinaryTree(TreeNode root) {
if(root.left==null&&root.right==null){
return 0;
}
diameterOfBinaryTreeSfs(root);
return res;
}
public int diameterOfBinaryTreeSfs(TreeNode root) {
if (root==null) {
return 0;
}
int l=diameterOfBinaryTreeSfs(root.left);
int r=diameterOfBinaryTreeSfs(root.right);
res=Math.max(res,l+r);
return Math.max(l,r)+1;//只返回左右路径最深的，因为这里返回后是回到了父节点，父节点只希望知道子树中最深的路径长度。为什么加一，因为父节点也算一个节点。
}
}
这题其实算不上很难，可能对递归理解不深的同学看代码会困难，但是这应该也是最大的难点了。