LeetCode hot100——二叉树的深度

题目给你一棵二叉树的根节点返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点root。两节点之间路径的长度由它们之间边数表示。示例 1输入root [1,2,3,4,5]输出3解释3 取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。示例 2输入root [1,2]输出1提示树中节点数目在范围[1, 104]内-100 Node.val 100题解/** * Definition for a binary tree node. * public 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; * } * } */ class Solution { int maxDiameter 0; public int diameterOfBinaryTree(TreeNode root) { dfs(root); return maxDiameter; } // 返回当前节点子树的最大深度节点数 private int dfs(TreeNode node) { if(node null) return 0; int leftDepth dfs(node.left); int rightDepth dfs(node.right); // 当前节点作为最高点左右深度相加就是边数 maxDiameter Math.max(maxDiameter, leftDepth rightDepth); // 返回当前子树最大深度 return Math.max(leftDepth, rightDepth) 1; } }思路某一个节点作为路径最高点时直径 左子树深度 右子树深度边的数量递归求树的最大深度同时维护一个全局变量记录遍历过程中出现过的最大直径。递归函数返回的是以当前节点为根的子树的最大深度。