本文主要是介绍【重点】【DFS】543.二叉树的直径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
法1：DFS两遍
不太好的方法
class Solution {public int diameterOfBinaryTree(TreeNode root) {if (root == null) {return 0;}int left = diameterOfBinaryTree(root.left);int right = diameterOfBinaryTree(root.right);int cur = oneSideDepth(root.left) + oneSideDepth(root.right);return Math.max(cur, Math.max(left, right));}public int oneSideDepth(TreeNode node) {if (node == null) {return 0;} return Math.max(oneSideDepth(node.left), oneSideDepth(node.right)) + 1;}
}
法2：最佳DFS
设置全局变量！简化DFS!
class Solution {int res = 0;public int diameterOfBinaryTree(TreeNode root) {if (root == null) {return 0;}maxDepth(root);return res;}public int maxDepth(TreeNode node) {if (node == null) {return 0;}int left = maxDepth(node.left);int right = maxDepth(node.right);res = res >= left + right ? res : left + right;return 1 + Math.max(left, right);}
}
这篇关于【重点】【DFS】543.二叉树的直径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
