110.平衡二叉树
题目链接：力扣
思路
这一道题目算是求数的最大高度的升级版，求树的最大高度采用的是后序遍历
先左记录、再右记录、再中处理
那么判断一棵树是不是平衡二叉树我们不仅需要记录它的最大高度，还要判断子树是不是一棵平衡二叉树
如果不是平衡二叉树，它的最大高度就没有记录的必要了，但是需要对此做出标记
平衡二叉树
递归法
求树的高度是使用后序遍历
这道题目不太好写的部分是递归函数“中”的部分不好写
因为以前在对节点遍历之后，都是处理一件事就可以了，但是这次不仅要记录这个节点的最大高度返回给父节点，还要判断自己是不是一个平衡二叉树
所以在处理节点的过程中，如果这个节点树是二平衡二叉树，我们就记录这棵树的最大高度，返回给上一层，如果不是平衡二叉树，那就给最大高度赋值-1，返回给上一层
class Solution { public boolean isBalanced(TreeNode root) { return getHight(root) == -1 ? false : true; } public int getHight(TreeNode root) { if (root == null) { return 0; } // 左 // 记录树的最大高度 int leftHight = getHight(root.left); // 判断树是否是平衡二叉树 if (leftHight == -1) { return -1; } // 右 // 记录数的最大高度 int rightHight = getHight(root.right); if (rightHight == -1) { return -1; } // 中 int result; // 判断该树是否是平衡二叉树 if (Math.abs(rightHight - leftHight) > 1) { result = -1; } else { result = 1 + Math.max(rightHight,leftHight); } return result; } }
迭代法
这道题目使用迭代法太复杂了，二刷再看
257.二叉树的所有路径
题目链接：力扣
思路
题目的要求是记录二叉树中的每一条路径，这种情况下我们就要使用前序遍历对二叉树进行处理了，中 左 右 的顺序，这样才方便父节点指向孩子节点，找到对应的路径
但是每记录一条路径之后，就遍历到了最下面的叶子节点，怎么才能开始从头走第二条道路呢，这就涉及到了回溯的思想，简单来说，就是回退
再许多情况下，回溯算法相当于穷举搜索的巧妙实现
类似的题目：112 113
二叉树的所有路径
递归法
第一步：递归函数的函数参数以及返回值
我们需要传入根节点，要查看的二叉树；
需要记录每一条路径的path
需要存放的结果集result
第二步：确认递归的终止条件
这道题的终止条件是找到叶子节点才算终止
第三步：单层结构的处理
回溯与递归是一一对应的，有一个递归就要有一个回溯，所以回溯要和递归永远在一起，写在一个花括号之内
暂时对回溯算法有了初步了解，回溯算法比较难理解的就是递归中的每次回溯，其实调用的递归函数还有自己的回溯，进去是啥，出了递归只是比进去的多了一个节点，所以除掉最后一个就可以了。剩下的在递归里面已经去除干净了
class Solution { public List<String> binaryTreePaths(TreeNode root) { // 用于保存最后的所有路径 List<String> result = new ArrayList<>(); if (root == null) { return result; } // 用于保存每条路径上的节点 List<Integer> nodes = new ArrayList<>(); // 调用收集函数 traversal(root,nodes,result); return result; } // 递归函数 public void traversal(TreeNode root,List<Integer> nodes,List<String> result) { // 中 // 如果这个节点是叶子节点，要确保这个节点可以添加到路径中，这是根据终止条件来的 nodes.add(root.val); // 终止条件 if (root.left == null && root.right == null) { // 说明你这条路径走到头了 nodes也将这条路径上的所有元素都添加上去了 // 这条路径已经成了，那就将这条路径转换成符合要求的格式 StringBuilder sb = new StringBuilder(); for (int i = 0; i < nodes.size () - 1; i++) { // 长度-1是因为最后一个节点不添加-> sb.append(nodes.get(i) + "->"); } sb.append(nodes.get(nodes.size () - 1)); // 将这条路径转换成字符串之后，再添加到结果集中 result.add(sb.toString()); return; } if (root.left != null) { traversal(root.left,nodes,result); // 这条语句执行完成之后，说这条路径从这个左节点开始已经记录完成了 nodes.remove(nodes.size() - 1); // 回溯 } if (root.right != null) { traversal(root.right,nodes,result); nodes.remove(nodes.size() - 1); // 回溯 } } }
迭代法
暂时搁置这种方法的学习，后面再学
404.左叶子之和
题目链接：力扣
思路
这道题是你找到左叶子，左叶子无法在自身节点上面判断自己是不是左叶子，必须借助节点的父节点来判断其左孩子是不是左叶子
左叶子是什么：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点
这道题的关键就是要知道怎么筛选出左叶子节点，并对其进行处理
if (node.left != null && node.left.left == null && node.left.right == null) { 这个才是左叶子 }
左叶子之和
递归法
因为我们是要统计根节点的左右子树的左叶子数之和，所以采用后序遍历，收集左右的左叶子数之和，然后再对两边的和进行处理
class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 0; } // 左 int leftNum = sumOfLeftLeaves(root.left); // 右 int rightNum = 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 +leftNum + rightNum; return sum; } }
迭代法
迭代法是比较好理解的，但需要注意的是，就是正常的层序遍历，只是在层序遍历的时候，对符合左叶子的节点进行收割
class Solution { public int sumOfLeftLeaves(TreeNode root) { // 采用层序遍历 Deque<TreeNode> deque = new LinkedList<>(); // 先将根节点入队 deque.offer(root); int sum = 0; while (!deque.isEmpty()) { int len = deque.size(); for (int i = 0; i < len; i++) { TreeNode node = deque.poll(); // 添加左子节点 if (node.left != null) { deque.offer(node.left); } // 添加右子节点 if (node.right != null) { deque.offer(node.right); } // 整个程序中，只有出现左叶子的时候，对左叶子的结果进行收割 if (node.left != null && node.left.left == null && node.left.right == null) { sum = sum + node.left.val; } } } return sum; } }
