此篇博客主要记录使用递归求解的树相关的算法题。
104. 给定一个二叉树，找出其最大深度。 （easy） 2021-01-13
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
常规递归题目。
110.平衡二叉树 （easy） 2021-01-14
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
题解：这道easy题目难度大于很多medium。最大的难点在于返回值的选择。使用递归时，如果返回左右子树是否为平衡二叉树，但是左右都是平衡二叉树不能说明就是平衡二叉树，还要左右子树的高度差小于1。如果递归返回高度信息也不合适，左右子树的高度差小于也证明不了平衡二叉树。
照着这个思路，可以编写一个返回结点的类，包含此结点的高度信息和是否平衡信息，递归函数返回此结点。
分析到这儿，就能想出更简便的方法了。设置一个全局变量，布尔型。递归函数的返回值使用树的高度，只要左右子树的高度信息相差大于1，则变量成true。
class Solution { boolean flag = true; public boolean isBalanced(TreeNode root) { depth(root); return flag; } public int depth(TreeNode root){ if(root == null){ return 0; } int l = depth(root.left); int r = depth(root.right); if(Math.abs(l - r) > 1){ //多一个判断标志 flag = false; } return Math.max(l , r) + 1; } }
543.二叉树的直径 (easy) 2021-01-14
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
题解：这一题与上一题及其相似。使用递归返回树的高度信息，定义一个全局变量记录当前结点的直径。每个结点的直径就是左子树长度加右子树长度，当然直径一直取较大值。
class Solution { int diameter; public int diameterOfBinaryTree(TreeNode root) { depth(root); return diameter; } public int depth(TreeNode root){ if(root == null){ return 0; } int l = depth(root.left); int r = depth(root.right); int nowDiameter = l + r; diameter = (diameter > nowDiameter) ? diameter : nowDiameter; return Math.max(l, r) + 1; } }
226.翻转二叉树 （easy）2021-01-14
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：4
/ \
7 2
/ \ / \
9 6 3 1
常规递归求解的题目。
class Solution { public TreeNode invertTree(TreeNode root) { if(root == null){ return null; } TreeNode tempNode = invertTree(root.left); root.left = invertTree(root.right); root.right = tempNode; return root; } }
617.合并二叉树 (easy) 2021-01-14
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始
常规递归的思路，就是内存占用较大，击败6%，诶。
class Solution { public TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if(t1 == null) return t2; if(t2 == null) return t1; t1.left = mergeTrees(t1.left, t2.left); t1.right = mergeTrees(t1.right, t2.right); t1.val = t1.val + t2.val; //以t1为主 return t1; } }
112.路径总和 （easy） 2021-01-14
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
这个测试用例绝了。
class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root == null) return false; if(root.left == null && root.right == null && root.val == sum){ return true; } boolean l = hasPathSum(root.left, sum - root.val); boolean r = hasPathSum(root.right, sum - root.val); return l || r ; } }
437.路径总和 （medium） 2021-01-14
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
题解：如果不是刚刚做了上面那个路径总和的题，这个题恐怕连思路都没。
花了一个小时，结果时间击败10%， 空间击败12%，纪念一下，哈哈。
class Solution { int count = 0; public int pathSum(TreeNode root, int sum) { if(root == null) return 0; preOrder(root, sum); return count; } //前序遍历 public void preOrder(TreeNode root, int sum){ subtatal(root, sum); if(root.left != null){ preOrder(root.left, sum); } if(root.right != null){ preOrder(root.right, sum); } } //写一个函数判断以此结点为根结点时，是否有数值和满足的情况 public int subtatal(TreeNode root, int sum){ if(root == null){ return count; } if(root != null && root.val == sum){ count ++; //如果返回则忽略了后面正负数和为0的情况。 //但是没有返回值，这个递归函数一直是false，虽然不需要用它的返回值 //return true; } int l = subtatal(root.left, sum - root.val); int r = subtatal(root.right, sum - root.val); return count; } }
原文：https://www.cnblogs.com/nobita/p/14276387.html