1. return if root is null 2. if root is a leaf node: 3. answer = max(answer, depth) // update the answer if needed 4. maximum_depth(root.left, depth + 1) // call the function recursively for left child 5. maximum_depth(root.right, depth + 1) // call the function recursively for right child
以下示例可帮助您了解其工作原理:
Java 参考代码:
1 2 3 4 5 6 7 8 9 10 11
privateint answer; // don't forget to initialize answer before call maximum_depth privatevoidmaximum_depth(TreeNode root, int depth){ if (root == null) { return; } if (root.left == null && root.right == null) { answer = Math.max(answer, depth); } maximum_depth(root.left, depth + 1); maximum_depth(root.right, depth + 1); }
1. return specific value for null node 2. left_ans = bottom_up(root.left) // call function recursively for left child 3. right_ans = bottom_up(root.right) // call function recursively for right child 4. return answers // answer <-- left_ans, right_ans, root.val
让我们继续讨论有关最大深度的问题,但使用另一种思考方式:对于树的单个节点,以自身为根的子树的最大深度 x 将是多少?
如果我们知道以其左孩子为根的子树的最大深度 l 和以其右孩子为根的子树的最大深度 r,我们可以回答前面的问题吗?当然可以,我们可以选择它们之间的最大值,然后加1以获取根于当前节点的子树的最大深度。即 x = max(l, r) + 1。
return (r1.val == r2.val and self.isSym(r1.left, r2.right) and self.isSym(r1.right, r2.left))
路径总和
给定一个二叉树和一个和,确定该树是否具有从根到叶的路径,以使该路径上的所有值加起来等于给定的和。
注意:叶是没有子节点的节点。
例:给定下面的二叉树,并且 sum = 22,
1 2 3 4 5 6 7
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
返回true,因为存在从根到叶的路径 5->4->11->2,其总和为22。
java 参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution{ publicbooleanhasPathSum(TreeNode root, int sum){ if (root == null) returnfalse; return hasPathSum(root, sum, 0); }
privatebooleanhasPathSum(TreeNode root, int sum, int cur){ cur += root.val; if (root.left == null && root.right == null) return sum == cur; boolean flag = false; if (root.left != null) flag = hasPathSum(root.left, sum, cur); if (!flag && root.right != null) flag = hasPathSum(root.right, sum, cur); return flag; } }