联网站,在线花钱做网站,寻找在山西运城专业做网站推广的,少儿编程加盟品牌排行榜TOC 前言 代码随想录算法训练营day17 一、Leetcode 110.平衡二叉树 1.题目 给定一个二叉树#xff0c;判断它是否是高度平衡的二叉树。 本题中#xff0c;一棵高度平衡二叉树定义为#xff1a; 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1#x… TOC 前言 代码随想录算法训练营day17 一、Leetcode 110.平衡二叉树 1.题目 给定一个二叉树判断它是否是高度平衡的二叉树。 本题中一棵高度平衡二叉树定义为 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 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] 内
-104 Node.val 104 来源力扣(LeetCode) 链接https://leetcode.cn/problems/balanced-binary-tree 2.解题思路 解题思路 方法一自顶向下的递归 定义函数 heightheight用于计算二叉树中的任意一个节点 pp 的高度 height(p){0p 是空节点max(height(p.left),height(p.right))1p 是非空节点height(p){0max(height(p.left),height(p.right))1p 是空节点p 是非空节点 有了计算节点高度的函数即可判断二叉树是否平衡。具体做法类似于二叉树的前序遍历即对于当前遍历到的节点首先计算左右子树的高度如果左右子树的高度差是否不超过 11再分别递归地遍历左右子节点并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。 3.代码实现 java class Solution { public boolean isBalanced(TreeNode root) { if (root null) { return true; } else { return Math.abs(height(root.left) - height(root.right)) 1 isBalanced(root.left) isBalanced(root.right); } } public int height(TreeNode root) {if (root null) {return 0;} else {return Math.max(height(root.left), height(root.right)) 1;}
} } 二、Leetcode 257. 二叉树的所有路径 1.题目 给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。 叶子节点 是指没有子节点的节点。 示例 1 输入root [1,2,3,null,5] 输出[1-2-5,1-3] 示例 2 输入root [1] 输出[1] 提示 树中节点的数目在范围 [1, 100] 内
-100 Node.val 100 来源力扣(LeetCode) 链接https://leetcode.cn/problems/binary-tree-paths 2.解题思路 方法一深度优先搜索 思路与算法 最直观的方法是使用深度优先搜索。在深度优先搜索遍历二叉树时我们需要考虑当前的节点以及它的孩子节点。 如果当前节点不是叶子节点则在当前的路径末尾添加该节点并继续递归遍历该节点的每一个孩子节点。
如果当前节点是叶子节点则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径将该路径加入到答案即可。 如此当遍历完整棵二叉树以后我们就得到了所有从根节点到叶子节点的路径。当然深度优先搜索也可以使用非递归的方式实现这里不再赘述。 3.代码实现 java class Solution { public List binaryTreePaths(TreeNode root) { List paths new ArrayList(); constructPaths(root, , paths); return paths; } public void constructPaths(TreeNode root, String path, ListString paths) {if (root ! null) {StringBuffer pathSB new StringBuffer(path);pathSB.append(Integer.toString(root.val));if (root.left null root.right null) { // 当前节点是叶子节点paths.add(pathSB.toString()); // 把路径加入到答案中} else {pathSB.append(-); // 当前节点不是叶子节点继续递归遍历constructPaths(root.left, pathSB.toString(), paths);constructPaths(root.right, pathSB.toString(), paths);}}
} } 三、Leetcode 404.左叶子之和 v 1.题目 给定二叉树的根节点 root 返回所有左叶子之和。 示例 1 输入: root [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中有两个左叶子分别是 9 和 15所以返回 24 示例 2: 输入: root [1] 输出: 0 提示: 节点数在 [1, 1000] 范围内
-1000 Node.val 1000 来源力扣(LeetCode) 链接https://leetcode.cn/problems/sum-of-left-leaves 2.解题思路 方法一深度优先搜索 3.代码实现 java class Solution { public int sumOfLeftLeaves(TreeNode root) { return root ! null ? dfs(root) : 0; } public int dfs(TreeNode node) {int ans 0;if (node.left ! null) {ans isLeafNode(node.left) ? node.left.val : dfs(node.left);}if (node.right ! null !isLeafNode(node.right)) {ans dfs(node.right);}return ans;
}public boolean isLeafNode(TreeNode node) {return node.left null node.right null;
} }
