【重点】【二叉树】543. 二叉树的直径

题目

法1:自己想的垃圾算法

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

法2:DFS好方法

合理利用全局变量, 可以大大简化问题!!!

class Solution {int ans = 0;public int diameterOfBinaryTree(TreeNode root) {if (root == null) {return 0;}maxDepth(root);return ans;}public int maxDepth(TreeNode root) {if (root == null) {return 0;}int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);ans = ans > leftDepth + rightDepth ? ans : leftDepth + rightDepth;return 1 + Math.max(leftDepth, rightDepth);}}