二叉树的 DFS 面试题通常考递归因为树本身就是递归结构。一、路径总和publicbooleanhasPathSum(TreeNoderoot,inttargetSum){if(rootnull)returnfalse;if(root.leftnullroot.rightnull){returnroot.valtargetSum;}returnhasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);}二、最近公共祖先publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(rootnull||rootp||rootq)returnroot;TreeNodeleftlowestCommonAncestor(root.left,p,q);TreeNoderightlowestCommonAncestor(root.right,p,q);if(left!nullright!null)returnroot;returnleft!null?left:right;}三、二叉树的直径classSolution{privateintdiameter0;publicintdiameterOfBinaryTree(TreeNoderoot){depth(root);returndiameter;}privateintdepth(TreeNodenode){if(nodenull)return0;intleftDepthdepth(node.left);intrightDepthdepth(node.right);diameterMath.max(diameter,leftDepthrightDepth);returnMath.max(leftDepth,rightDepth)1;}} 觉得有用的话点赞 关注【张老师技术栈】吧
二叉树的 DFS 面试题通常考递归因为树本身就是递归结构。一、路径总和publicbooleanhasPathSum(TreeNoderoot,inttargetSum){if(rootnull)returnfalse;if(root.leftnullroot.rightnull){returnroot.valtargetSum;}returnhasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);}二、最近公共祖先publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(rootnull||rootp||rootq)returnroot;TreeNodeleftlowestCommonAncestor(root.left,p,q);TreeNoderightlowestCommonAncestor(root.right,p,q);if(left!nullright!null)returnroot;returnleft!null?left:right;}三、二叉树的直径classSolution{privateintdiameter0;publicintdiameterOfBinaryTree(TreeNoderoot){depth(root);returndiameter;}privateintdepth(TreeNodenode){if(nodenull)return0;intleftDepthdepth(node.left);intrightDepthdepth(node.right);diameterMath.max(diameter,leftDepthrightDepth);returnMath.max(leftDepth,rightDepth)1;}} 觉得有用的话点赞 关注【张老师技术栈】吧
