LeetCode:110.平衡二叉树
110.平衡二叉树-力扣（leetcode）
1.思路
迭代法似乎更好理解，但是实现起来操作细节略复杂；
递归：
明确问题：求高度差（后续遍历：保证左右节点先触达叶子节点）
确定递归函数的参数和返回值：return getHeight(root) != -1;
确定终止条件：Math.abs(leftHeight - rightHeight) > 1
任何一个节点的左右子树高度差大于1，即刻终止返回。
确定单层递归的逻辑：private int getHeight(TreeNode root){左-右-终止条件-中}（见代码）
2.代码实现
1class Solution { 2 public boolean isBalanced(TreeNode root) { 3 // 确定递归函数的参数及返回值 4 return getHeight(root) != -1; 5 6 } 7 private int getHeight(TreeNode root) { 8 if (root == null) { 9 return 0; 10 } 11 int leftHeight = getHeight(root.left); // 左 12 if (leftHeight == -1) { 13 return -1; 14 } 15 int rightHeight = getHeight(root.right); // 右 16 if (rightHeight == -1) { 17 return -1; 18 } 19 // 当任意一个节点的左右子树高度差大于1时， return -1表示已经不是平衡树了 20 if (Math.abs(leftHeight - rightHeight) > 1) { 21 return -1; 22 } 23 return Math.max(leftHeight, rightHeight) + 1; // 中 24 } 25}
3.复杂度分析
时间复杂度：O(n),其中 n 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)
空间复杂度：O(n),其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过n。（实际上最坏情况应该是n左右，因为叶子节点都调用了两次）
LeetCode:257. 二叉树的所有路径
1.思路
确定返回结果：根节点到叶子节点的所有路径，故采用前序遍历
递归三部曲：
确定递归函数的参数及返回值：traversal(root, paths, res);
确定单层递归的逻辑：
什么时间记录路径？？什么时间终止什么时间记录路径。当节点的左右孩子均为null时(确定终止条件)，记录路径。
左遍历；
右遍历；
2.代码实现
1class Solution { 2 public List<String> binaryTreePaths(TreeNode root) { 3 // 返回值为根节点——叶子节点的路径。显然，是前序遍历。 4 List<String> res = new ArrayList<>(); // 存储最终结果 5 List<Integer> paths = new ArrayList<>(); 6 traversal(root, paths, res); 7 return res; 8 } 9 private void traversal(TreeNode root, List<Integer> paths, List<String> res) { 10 // 前序，放入中间节点 11 paths.add(root.val); 12 // 遇到叶子节点 13 if (root.left == null && root.right == null) { 14 // 输出该路径 15 StringBuilder sb = new StringBuilder(); 16 for (int i = 0; i < paths.size() - 1; i++) { 17 sb.append(paths.get(i)).append("->"); 18 } 19 sb.append(paths.get(paths.size() - 1)); // 记录最后一个节点 20 res.add(sb.toString()); // 收集一个路径 21 return; // 回溯 22 } 23 // 左遍历，递归 + 回溯 24 if (root.left != null) { 25 traversal(root.left, paths, res); 26 paths.remove(paths.size() - 1); 27 } 28 // 右遍历 29 if (root.right != null) { 30 traversal(root.right, paths, res); 31 paths.remove(paths.size() - 1); 32 } 33 } 34 }
3.复杂度分析
时间复杂度：O(n²)，其中N表示节点数目，递归时每个节点访问一次，同时会对path变量进行拷贝，时间代价也为O(n)，故时间复杂度为O(n²)；
空间复杂度：O(n²)和O(logn)²，其中N表示节点数目,除了答案数组，还需要考虑递归调用的栈空间。在最坏情况下，当二叉树中每个节点只有一个孩子节点时，即整棵二叉树呈一个链状，此时递归的层数为 N，此时每一层的 path 变量的空间代价的总和为 O(N²)最好情况下，当二叉树为平衡二叉树时，它的高度为 为logN,此时空间复杂度为O(logN)²。
LeetCode:404.左叶子之和
1.思路
返回结果：左叶子之和。显然采用后序遍历，先递归到底层叶子节点，后收集左叶子节点的数值。关键在于左叶子节点的值判定
2.代码实现
1class Solution { 2 public int sumOfLeftLeaves(TreeNode root) { 3 if (root == null) return 0; 4 // if (root.left == null && root.right == null) return 0; // 叶子节点返回 0 5 int leftValue = sumOfLeftLeaves(root.left); 6 int rightValue = sumOfLeftLeaves(root.right); 7 8 int midValue = 0; 9 if (root.left != null && root.left.left == null && root.left.right == null) { 10 midValue = root.left.val; 11 } 12 int sum = midValue + leftValue + rightValue; 13 return sum; 14 } 15}
3.复杂度分析
时间复杂度：O(n),其中n是树中的节点个数
空间复杂度：O(n),空间复杂度与深度优先搜索使用的栈的最大深度相关。在最坏的情况下，树呈现链式结构，深度为 O(n)，对应的空间复杂度也为 O(n).
最近刷题，总是抄代码，有时候还有些疑问，真不舒服啊~~~
