本文主要是介绍代码随想录算法训练营第十七天 | 110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
[LeetCode] 110. 平衡二叉树
[LeetCode] 110. 平衡二叉树 文章解释
[LeetCode] 110. 平衡二叉树 视频解释
给定一个二叉树，判断它是否是
平衡二叉树
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：true示例 2：
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false示例 3：
输入：root = [] 输出：true提示：
- 树中的节点数在范围
[0, 5000]内-10^4 <= Node.val <= 10^4
自己看到题目的第一想法
1. 什么是平衡二叉树, 平衡二叉树的具体定义是什么呢?
看完代码随想录之后的想法
1. 平衡二叉树的定义: 每一个节点的左子树和右子树的高度叉不大于一, 则说当前二叉树为平衡二叉树.
2. 根据定义可以很本能的想到使用递归法来判断是否平衡二叉树. 假设当前节点为 node, 则先计算 node.left 的高度, 再计算 node.right 的高度. 如果 node.left 和 node.right 的差的绝对值大于 1, 则说明当前节点的左右子树破坏了平衡, 因此整颗树都不是平衡二叉树. 此时返回 -1. 如果 node.left 和 node.right 的差的绝对值不大于 1, 则将两者中的大者加一后, 返回给上一层函数.
3. 一定要记得, 这里是要判断每一个节点是否平衡, 不是只单单判断跟节点的左右节点是否高度上满足平衡条件.
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
// 递归法
class Solution {public boolean isBalanced(TreeNode root) {if (root == null) {return true;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return leftHeight != -1 && rightHeight != -1 && Math.abs(leftHeight - rightHeight) <= 1;// 这个条件老是忘记}private int getHeight(TreeNode node) {if (node == null) {return 0;} if (node.left == null && node.right == null) {return 1;} else {int leftHeight = getHeight(node.left);if (leftHeight == -1) { // 这个条件老是忘记return -1;}int rightHeight = getHeight(node.right);if (rightHeight == -1) { // 这个条件老是忘记return rightHeight;}if (Math.abs(leftHeight - rightHeight) > 1) {return -1;} else {return Math.max(leftHeight, rightHeight) + 1;}}}
}/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
// 迭代法
class Solution {public boolean isBalanced(TreeNode root) {if (root == null) {return true;}Stack<TreeNode> nodes = new Stack<>();TreeNode node = null;nodes.push(root);int leftHeight = 0;int rightHeight = 0;while (!nodes.isEmpty()) {node = nodes.pop();leftHeight = getHeight(node.left);rightHeight = getHeight(node.right);if (Math.abs(leftHeight - rightHeight) > 1) {return false;}if (node.right != null) {nodes.push(node.right);}if (node.left != null) {nodes.push(node.left);}}return true;}private int getHeight(TreeNode node) {if (node == null) {return 0;}Stack<TreeNode> nodes = new Stack<>();int maxDepth = 0;int depth = 0;nodes.push(node);while (!nodes.isEmpty()) {node = nodes.pop();if (node != null) {nodes.push(node);nodes.push(null);depth++;if (node.right != null) {nodes.push(node.right);}if (node.left != null) {nodes.push(node.left);}} else {nodes.pop();depth--;}if (maxDepth < depth) {maxDepth = depth;}}return maxDepth;}
}自己实现过程中遇到哪些困难
1. 遇到了一个定义上理解错误的地方. 平衡二叉树的平衡, 说的是每个节点都是平衡的, 而不单单指跟节点的左右子节点是平衡的. 最极端的例子, 一个跟节点, 左节点开始的每个节点只有左节点, 右节点开始的每个节点只有右节点, 假设跟节点的左右子树高度都是3, 这时候当前子树并不是平衡的.
2. 计算平衡二叉树高度的时候, 老是忘记判断迭代返回高度值为 -1 的情况. 说明对平衡二叉树的判断逻辑还掌握的不够清楚和彻底. 写博客的意义更多的是理清思路, 整理架构. 而现在的模式更像是在记流水账. 需要反思.
[LeetCode] 257. 二叉树的所有路径
[LeetCode] 257. 二叉树的所有路径 文章解释
[LeetCode] 257. 二叉树的所有路径 视频解释
自己看到题目的第一想法
解决的思路:
1. 首先, 需要遍历整个二叉树.
2. 当遇到叶子结点的时候, 记录一下当前的路径.
3. 当遇到叶子结点并且记录过路径后, 需要将叶子结点从路径中删除.
疑惑点:
如何找到当前叶子结点的上一个节点呢, 只有找到上一个节点, 才能继续遍历.
看完代码随想录之后的想法
1. 递归法: 递归法的逻辑就是把所有遍历到的元素添加到路径列表里, 同时传给下一个子节点. 这样当到达叶子结点时, 叶子结点就知道从根节点到自己的路径是什么.
2. 迭代法: 通过迭代法遍历元素,
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/// 递归解法1: 效率一般 49.36%
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();binaryTreePaths(root, new ArrayList<Integer>(), result);return result;}private void binaryTreePaths(TreeNode node, List<Integer> paths, List<String> result) {if (node == null) {return;}paths.add(node.val);StringBuilder strBuilder = new StringBuilder();if (node.left == null && node.right == null) {for (int i = 0; i < paths.size() - 1; i++) {strBuilder.append(paths.get(i) + "->");}strBuilder.append(paths.get(paths.size() - 1));result.add(strBuilder.toString());paths.remove(paths.size() - 1);return;}if (node.left != null) {binaryTreePaths(node.left, paths, result);}if (node.right != null) {binaryTreePaths(node.right, paths, result);}paths.remove(paths.size() - 1);}
}/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/// 递归解法 1 的 StringBuilder 优化版:
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();binaryTreePaths(root, "", result);return result;}private void binaryTreePaths(TreeNode node, String path, List<String> result) {if (node == null) {return;}StringBuilder strBuilder = new StringBuilder(path);strBuilder.append(node.val);if (node.left == null && node.right == null) {result.add(strBuilder.toString());return;}strBuilder.append("->");if (node.left != null) {binaryTreePaths(node.left, strBuilder.toString(), result);}if (node.right != null) {binaryTreePaths(node.right, strBuilder.toString(), result);}}
}/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/// 迭代法: 49.36%
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> nodes = new Stack<>();List<Integer> paths = new ArrayList<>();TreeNode node = null;nodes.push(root);while (!nodes.isEmpty()) {node = nodes.pop();if (node != null) {if (node.left == null && node.right == null) {StringBuilder strBuilder = new StringBuilder();for (int i = 0; i < paths.size(); i++) {strBuilder.append(paths.get(i)).append("->");}strBuilder.append(node.val);result.add(strBuilder.toString());}nodes.push(node);nodes.push(null);paths.add(node.val);if (node.right != null) {nodes.push(node.right);}if (node.left != null) {nodes.push(node.left);}} else {nodes.pop();paths.remove(paths.size() - 1);}}return result;}
}[LeetCode] 404. 左叶子之和
[LeetCode] 404. 左叶子之和 文章解释
[LeetCode] 404. 左叶子之和 视频解释
自己看到题目的第一想法
先看了视频, 所以好像没有什么自己的思考.
1. 遍历二叉树, 遇到叶子结点的时候, 判断一下当前节点是不是左节点, 是的话将值加入到统计中.
2. 遍历二叉树的时候不知道当前节点是否是父节点的左节点, 可以采用递归的方式, 将当前节点的父节点传递下来, 或者用一个变量标记当前节点是否是左节点.
3. 好像整体也没有很难.
看完代码随想录之后的想法
1. 最核心的部分就是, 如果不使用额外信息的时候. 我们在递归三部曲的循环结束条件中, 需要添加对左侧叶子结点的判断. 即 node.left != null && node.left.left != null && node.left.right != null.
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
// 递归解法
class Solution {public int sumOfLeftLeaves(TreeNode root) {if (root == null) {return 0;}int leftTreeSum = 0;int rightTreeSum = 0;if (root.left != null && root.left.left == null && root.left.right == null) {leftTreeSum = root.left.val;} else {leftTreeSum = sumOfLeftLeaves(root.left);}rightTreeSum = sumOfLeftLeaves(root.right);return leftTreeSum + rightTreeSum;}
}/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
// 迭代解法
class Solution {public int sumOfLeftLeaves(TreeNode root) {if (root == null) {return 0;}Stack<TreeNode> nodes = new Stack<>();TreeNode node = null;nodes.push(root);int sum = 0;while (!nodes.isEmpty()) {node = nodes.pop();if (node.right != null) {nodes.push(node.right);}if (node.left != null && node.left.left == null&& node.left.right == null) {sum += node.left.val;} else if (node.left != null) {nodes.push(node.left);}}return sum;}
}自己实现过程中遇到哪些困难
使用迭代实现的时候, 很难想到什么时候要用标记法, 什么时候不需要.
虽然递归的单次循环条件也时常想不明白, 但是整体来说, 递归方案会更容易调试出来.
要怎么梳理, 才能让自己掌握得更好呢?
这篇关于代码随想录算法训练营第十七天 | 110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
