1. LeetCode 110. 平衡二叉树
1.1 思路
- 平衡二叉树：任何节点的左右子树的高度差小于等于1
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。求深度按道理应该是前序遍历
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。求高度按道理应该是后序遍历
- 递归函数的参数和返回值：返回值是高度，参数是TreeNode。这里注意我们判断任何一个节点的左右子树的高度差时，如果发现高度差大于1了返回时就返回-1，就告诉上一层这棵树已经不是平衡的了，一个节点一个节点的往上返回，最后告诉根节点不是平衡的
- 终止条件：如果节点为空就返回0，空节点是没有高度的
- 单层递归的逻辑：左子树int leftHeight=getHeight(node.left); 如果左子树高度==-1，那就往上返回-1；右子树int rightHeight=getHeight(node.right); 如果右子树高度==-1，那就往上返回-1；如果左右子树都符合平衡的条件，那就判断高度差，int result=（左子树-右子树）的高度差的绝对值，如果大于1了，那就不符合，往上返回-1；如果不是，说明就符合条件了，那就返回 左子树和右子树之间的最大值+1 ，这个值就是基于左子树和右子树的高度的父节点的高度
- 以上采用的是后序遍历
1.2 代码
class Solution { /** * 递归法 */ public boolean isBalanced(TreeNode root) { return getHeight(root) != -1; } private int getHeight(TreeNode root) { if (root == null) { return 0; } int leftHeight = getHeight(root.left); if (leftHeight == -1) { return -1; } int rightHeight = getHeight(root.right); if (rightHeight == -1) { return -1; } // 左右子树高度差大于1，return -1表示已经不是平衡树了 if (Math.abs(leftHeight - rightHeight) > 1) { return -1; } return Math.max(leftHeight, rightHeight) + 1; } }
2. LeetCode 257. 二叉树的所有路径
2.1 思路
- 我们求路径的过程中使用前序遍历，为什么？因为这样我们才能让父节点指向孩子节点，这样才能按照路径的方式输出
- 这题递归就不得不提回溯，为什么有回溯？递归和回溯其实是相辅相成的，有递归就一定有回溯。那么这题为什么有回溯的过程呢？当我们用集合收集到一个路径以后就要把对应遍历过的元素回弹，这个过程就是一个回溯的过程
- 递归函数的参数和返回值：参数TreeNode，List<Integer>path，List<String>result，path集合存的是单条路径，result存的是所有的路径。我们直接添加到集合就不需要返回值了
- 终止条件：我们遍历到的节点左右孩子都为空就说明到了叶子节点，就是收获结果的时候，这时result.add(path)，这里需要把int类型的数据之间添加“->”转化为String，符合LeetCode的要求，然后return
- 单层处理逻辑：前序遍历“根左右”，处理过程就是要把路径的值添加到path中，但这里注意！我们处理“根”要在终止条件之前，path.add(node.val)。因为如果“根”写在终止条件以下，就会把叶子节点落下，因为直接return了。然后是“左”，向左遍历时（向右也是），要判断一下node.left是否为空，不为空才去遍历，避免终止条件上发生空指针异常，判断之后就递归函数(node.left, path, result)，然后就是回溯
- 回溯的处理逻辑：path.remove(path.size() - 1)，这里是把刚加入的元素弹出了。这里回溯的解释看视频讲解
- 然后到“右”，右孩子不为空才遍历，递归函数(node.right, path, result)
2.2 代码
//解法一 //方式一 class Solution { /** * 递归法 */ public List<String> binaryTreePaths(TreeNode root) { List<String> res = new ArrayList<>();// 存最终的结果 if (root == null) { return res; } List<Integer> paths = new ArrayList<>();// 作为结果中的路径 traversal(root, paths, res); return res; } private void traversal(TreeNode root, List<Integer> paths, List<String> res) { paths.add(root.val);// 前序遍历，中 // 遇到叶子结点 if (root.left == null && root.right == null) { // 输出 StringBuilder sb = new StringBuilder();// StringBuilder用来拼接字符串，速度更快 for (int i = 0; i < paths.size() - 1; i++) { sb.append(paths.get(i)).append("->"); } sb.append(paths.get(paths.size() - 1));// 记录最后一个节点 res.add(sb.toString());// 收集一个路径 return; } // 递归和回溯是同时进行，所以要放在同一个花括号里 if (root.left != null) { // 左 traversal(root.left, paths, res); paths.remove(paths.size() - 1);// 回溯 } if (root.right != null) { // 右 traversal(root.right, paths, res); paths.remove(paths.size() - 1);// 回溯 } } }
3. LeetCode 404. 左叶子之和
3.1 思路
- 注意判断什么是左叶子，不要误解题目意思
- 这道题与以往不同，我们要找到的左叶子不能够遍历到它的时候才获取，因为这样只能知道它是不是叶子节点，但不知道是不是左叶子。因此我们要遍历到它的父节点的时候就判断左叶子。判断条件：左孩子不为空并且左孩子的左右孩子同时为空。符合条件才是我们要的左叶子
- 这题用后序遍历挺符合思路的，因为一层一层返回给上一层，父节点只要加上左子树的左叶子和右子树的左叶子即可
- 递归函数的参数和返回值：参数是TreeNode，返回值int。但这题不用额外定义函数了，直接用力扣的主函数即可
- 终止条件：第一个肯定是如果节点为空就返回0；第二个就是遇到叶子节点（左右孩子军为空）就返回0；这里是因为叶子节点我们要的是收集左子树和右子树的左叶子之和，都为空说明为0，因为左子树的左叶子为0，右子树的左叶子也为0
- 单层递归逻辑：int leftVal=函数(root.left)。int rightVal=函数(root.right)。判断条件：左孩子不为空并且左孩子的左右孩子同时为空，符合条件就进入leftVal=root.left.val 。int sum=leftVal+rightVal。然后return sum即可
3.2 代码
class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root == null) return 0; int leftValue = sumOfLeftLeaves(root.left); // 左 int rightValue = sumOfLeftLeaves(root.right); // 右 int midValue = 0; if (root.left != null && root.left.left == null && root.left.right == null) { midValue = root.left.val; } int sum = midValue + leftValue + rightValue; // 中 return sum; } }
