牛客NC195 二叉树的直径【simple DFS C++ / Java /Go/ PHP】

题目

在这里插入图片描述

题目链接：
https://www.nowcoder.com/practice/15f977cedc5a4ffa8f03a3433d18650d

思路

最长路径有两种情况：
1.最长条路径经过根节点，那么只需要找出根节点的左右两棵子树的最大深度然后相加即可。
2.最长路径没有经过根节点，那么只需要找出根节点的左子树或者根节点的右子树作为根的最长路径度即可。递归调用，自底向上查找子树的深度，如果某一个左子树与右子树深度之和大于当前纪录的直径，那么替换为当前直径，递归完成之后即可找出直径。

参考答案C++

/*** struct TreeNode {*  int val;*  struct TreeNode *left;*  struct TreeNode *right;*  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param root TreeNode类* @return int整型*/int diameterOfBinaryTree(TreeNode* root) {/*最长路径有两种情况：1.最长条路径经过根节点，那么只需要找出根节点的左右两棵子树的最大深度然后相加即可。2.最长路径没有经过根节点，那么只需要找出根节点的左子树或者根节点的右子树作为根的最长路径度即可。递归调用，自底向上查找子树的深度，如果某一个左子树与右子树深度之和大于当前纪录的直径，那么替换为当前直径，递归完成之后即可找出直径。*/if (root == nullptr)return 0;vector<TreeNode> q;q.push_back(*root);int ans = 0;while (q.size() > 0 ) {int size = q.size();vector<TreeNode> qbak;for (int i = 0; i < size; i++) {TreeNode pop = q[i];int h1 = height(pop.left);int h2 = height(pop.right);if ( ans < h1 + h2) {ans = h1 + h2;}if (pop.left != nullptr) {qbak.push_back(*pop.left);}if (pop.right != nullptr) {qbak.push_back(*pop.right);}}q = qbak;}return ans;}int height(TreeNode* node) {if (node == nullptr) return 0;int h1 = height(node->left);int h2 = height(node->right);if (h1 > h2) {return h1 + 1;}return h2 + 1;}
};

参考答案Java

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;*   public TreeNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param root TreeNode类* @return int整型*/public int diameterOfBinaryTree (TreeNode root) {/*最长路径有两种情况：1.最长条路径经过根节点，那么只需要找出根节点的左右两棵子树的最大深度然后相加即可。2.最长路径没有经过根节点，那么只需要找出根节点的左子树或者根节点的右子树作为根的最长路径度即可。递归调用，自底向上查找子树的深度，如果某一个左子树与右子树深度之和大于当前纪录的直径，那么替换为当前直径，递归完成之后即可找出直径。*/if (root == null) return 0;Queue<TreeNode> q = new LinkedList<>();q.add(root);int max = 0;while (!q.isEmpty()) {TreeNode pop = q.poll();int h1 = heigt(pop.left); //左树高度int h2 = heigt(pop.right); //右树高度if (max < h1 + h2) {max = h1 + h2;}if (pop.left != null) {q.add(pop.left);}if (pop.right != null) {q.add(pop.right);}}return max;}public int heigt(TreeNode node) {if (node == null) return 0;int h1 = heigt(node.left);int h2 = heigt(node.right);return Math.max(h1, h2) + 1;}
}

参考答案Go

package mainimport . "nc_tools"/** type TreeNode struct {*   Val int*   Left *TreeNode*   Right *TreeNode* }*//*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param root TreeNode类* @return int整型*/
func diameterOfBinaryTree(root *TreeNode) int {/*最长路径有两种情况：1.最长条路径经过根节点，那么只需要找出根节点的左右两棵子树的最大深度然后相加即可。2.最长路径没有经过根节点，那么只需要找出根节点的左子树或者根节点的右子树作为根的最长路径度即可。递归调用，自底向上查找子树的深度，如果某一个左子树与右子树深度之和大于当前纪录的直径，那么替换为当前直径，递归完成之后即可找出直径。*/if root == nil {return 0}q := []*TreeNode{}q = append(q, root)ans := 0for len(q) > 0 {size := len(q)qbak := []*TreeNode{}for i := 0; i < size; i++ {pop := q[i]h1 := height(pop.Left)h2 := height(pop.Right)if ans < h1+h2 {ans = h1 + h2}if pop.Left != nil {qbak = append(qbak, pop.Left)}if pop.Right != nil {qbak = append(qbak, pop.Right)}}q = qbak}return ans
}func height(node *TreeNode) int {if node == nil {return 0}h1 := height(node.Left)h2 := height(node.Right)if h1 > h2 {return h1 + 1}return h2 + 1
}

参考答案PHP

<?php/*class TreeNode{var $val;var $left = NULL;var $right = NULL;function __construct($val){$this->val = $val;}
}*//*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param root TreeNode类 * @return int整型*/
function diameterOfBinaryTree( $root )
{/*最长路径有两种情况：1.最长条路径经过根节点，那么只需要找出根节点的左右两棵子树的最大深度然后相加即可。2.最长路径没有经过根节点，那么只需要找出根节点的左子树或者根节点的右子树作为根的最长路径度即可。递归调用，自底向上查找子树的深度，如果某一个左子树与右子树深度之和大于当前纪录的直径，那么替换为当前直径，递归完成之后即可找出直径。*/if($root ==null){return 0;}$q = [$root];$max = 0;while (count($q) >0){$size =count($q);$qbak = [];for($i=0;$i<$size;$i++){$pop = $q[$i];$h1 = height($pop->left);$h2 = height($pop->right);if($max < $h1+$h2){$max = $h1+$h2;}if($pop->left!=null){$qbak[count($qbak)] = $pop->left;}if($pop->right!=null){$qbak[count($qbak)] = $pop->right;}}$q =$qbak;}return $max;
}function height($node){if($node ==null) return 0;$h1 = height($node->left);$h2 = height($node->right);if($h1 >$h2){return $h1+1;}return $h2+1;
}