# 最大深度 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 最大深度 —— 递归写法 ``` /* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function TreeDepth(pRoot) { if(pRoot === null) { return 0; } var left = pRoot.left, right = pRoot.right; return Math.max(TreeDepth(left),TreeDepth(right)) + 1; } ``` ``` function TreeDepth(pRoot) { if(pRoot === null) return 0; let left = TreeDepth(pRoot.left); let right = TreeDepth(pRoot.right); return Math.max(left,right) + 1; } ``` # 二叉树的直径长度。 一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。 ``` 易错点是直径可能不经过根节点 用max保存最大值， 当每个节点作为根节点时，与max比较进行更新 var diameterOfBinaryTree = function(root) { let max = 0; function dfs(root){ if(!root) return 0; let l = dfs(root.left); let r = dfs(root.right); max = Math.max(max,l+r); return Math.max(l,r)+1; } dfs(root); return max; }; ``` # 二叉树中的最大路径和 给定一个非空二叉树，返回其最大路径和。 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。 ``` var maxPathSum = function(root) { let max = -Infinity; function dfs(root){ if(!root) return 0; let l = Math.max(dfs(root.left),0); let r = Math.max(dfs(root.right),0); max = Math.max(max,l + r + root.val); return Math.max(l,r)+root.val; } dfs(root); return max; }; ```