【Hot100】LeetCode—543. 二叉树的直径

---

• 原题连接：543. 二叉树的直径

1- 思路

深搜——dfs

递归三部曲

• 1- 递归参数和返回值
  • 返回 public int depth(TreeNode root)
• 2- 终止条件
  • 如果遇到 null，则返回 0
• 3- 递归表达式
  • return Math.max(left,right)+1

---

2- 实现

⭐543. 二叉树的直径——题解思路

class Solution {int res = 0;public int diameterOfBinaryTree(TreeNode root) {depth(root);return res;}public int depth(TreeNode root){if(root==null){return 0;}int left = depth(root.left);int right = depth(root.right);res = Math.max(res,left+right);return Math.max(left,right)+1;}
}

---

3- ACM 实现

public class diameterOfBinaryTree {public static 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;}}public static TreeNode build(String str){if(str == null || str.length()==0){return null;}String input = str.replace("[","");input = input.replace("]","");String[] parts = input.split(",");Integer[] nums = new Integer[parts.length];for(int i = 0 ; i < parts.length;i++){if(!parts[i].equals("null")){nums[i] = Integer.parseInt(parts[i]);}else{nums[i] = null;}}Queue<TreeNode> queue = new LinkedList<>();TreeNode root = new TreeNode(nums[0]);queue.offer(root);int index = 1;while(!queue.isEmpty()&& index<parts.length){TreeNode node = queue.poll();if(index<nums.length && nums[index]!=null){node.left = new TreeNode(nums[index]);queue.offer(node.left);}index++;if(index<nums.length && nums[index]!=null){node.right = new TreeNode(nums[index]);queue.offer(node.right);}index++;}return root;}static int res = 0;public static int diameterOfBinaryTree(TreeNode root) {depth(root);return res;}public static int depth(TreeNode root){if(root==null){return 0;}int left = depth(root.left);int right = depth(root.right);res = Math.max(res,left+right);return Math.max(left,right)+1;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();TreeNode root = build(input);System.out.println("结果是"+diameterOfBinaryTree(root));}
}