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).
最近刷题,总是抄代码,有时候还有些疑问,真不舒服啊~~~