李氏牛仔网站建设风,如何给自己做网站,网站开发什么语言最好,浙江大学微纳加工平台110. 平衡二叉树
题目链接
题目描述#xff1a; 给定一个二叉树#xff0c;判断它是否是高度平衡的二叉树。
本题中#xff0c;一棵高度平衡二叉树定义为#xff1a;一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,nul…110. 平衡二叉树
题目链接
题目描述 给定一个二叉树判断它是否是高度平衡的二叉树。
本题中一棵高度平衡二叉树定义为一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7] 返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4] 返回 false 。
难点
二叉树节点的深度指从根节点到该节点的最长简单路径边的条数。二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数。
思路 要求比较高度必然是要后序遍历。
时间复杂度O() 空间复杂度O()
class Solution {public boolean isBalanced(TreeNode root) {if (root null) return true;return !(getHeight(root) -1);}private int getHeight(TreeNode root) {if (root null) return 0; //空结点高度为0int leftH getHeight(root.left);if (leftH -1) return -1;int rightH getHeight(root.right);if (rightH -1) return -1;return Math.abs(leftH-rightH) 1 ? -1 : 1Math.max(leftH, rightH);}
}时长 15min
收获 区分深度与高度 递归方法练习 257. 二叉树的所有路径
题目链接
题目描述 给定一个二叉树返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
难点
思路
时间复杂度O() 空间复杂度O()
class Solution {ListString resList new ArrayList();public ListString binaryTreePaths(TreeNode root) {if (root null) return resList;ListInteger path new ArrayList();traversal(root, path);return resList;}private void traversal(TreeNode root, ListInteger path) {path.add(root.val);if (root.left null root.right null) {StringBuilder sb new StringBuilder();for (int i 0; i path.size()-1; i) {sb.append(path.get(i)).append(-);}sb.append(path.get(path.size()-1));resList.add(sb.toString());return;}if (root.left ! null) {traversal(root.left, path);path.remove(path.size()-1);}if (root.right ! null) {traversal(root.right, path);path.remove(path.size()-1);}}
}如果想隐藏回溯要小心了
if (root.left ! null) {traversal(root.left, path.append(-));
}
if (root.right ! null) {traversal(root.right, path.append(-));
}这么写大错特错因为通过path.append方法字符串元素是累计添加到path中退出函数时并不能达到回溯的目的 正确的做法是new一个StringBuilder对象作为参数传入
class Solution {ListString resList new ArrayList();public ListString binaryTreePaths(TreeNode root) {if (root null) return resList;StringBuilder path new StringBuilder();traversal(root, path);return resList;}private void traversal(TreeNode root, StringBuilder path) {path.append(root.val);if (root.left null root.right null) {resList.add(path.toString());return;}if (root.left ! null) {traversal(root.left, new StringBuilder(path).append(-));}if (root.right ! null) {traversal(root.right, new StringBuilder(path).append(-));}}
}当然使用字符串拼接实现会更容易
ListString resList new ArrayList();public ListString binaryTreePaths(TreeNode root) {if (root null) return resList;String path ;traversal(root, path);return resList;}private void traversal(TreeNode root, String path) {path root.val;if (root.left null root.right null) {resList.add(path);return;}if (root.left ! null) {traversal(root.left, path-);}if (root.right ! null) {traversal(root.right, path-);}}迭代法
class Solution {public ListString binaryTreePaths(TreeNode root) {ListString result new ArrayList();if (root null)return result;StackObject stack new Stack();// 节点和路径同时入栈stack.push(root);stack.push(root.val );while (!stack.isEmpty()) {// 节点和路径同时出栈String path (String) stack.pop();TreeNode node (TreeNode) stack.pop();// 若找到叶子节点if (node.left null node.right null) {result.add(path);}//右子节点不为空if (node.right ! null) {stack.push(node.right);stack.push(path - node.right.val);}//左子节点不为空if (node.left ! null) {stack.push(node.left);stack.push(path - node.left.val);}}return result;}
}时长 13min
收获 注意拼接字符串的细节 404. 左叶子之和
题目链接
题目描述 计算给定二叉树的所有左叶子之和。
示例
难点
思路 找左叶子之和 核心判断当前节点是否有左孩子左孩子是否为叶子
时间复杂度O() 空间复杂度O()
这样写是不对的 变量值sum没有返回。。。什么原因
public int sumOfLeftLeaves(TreeNode root) {int sum 0;traversal(root, sum);return sum;
}
private void traversal(TreeNode root, int sum) {if (root null) return;if (root.left ! null root.left.left null root.left.right null) {sum root.left.val;}traversal(root.left, sum);traversal(root.right, sum);
}sum不能通过函数的形参传入
int sum 0;
public int sumOfLeftLeaves(TreeNode root) {traversal(root);return sum;
}
private void traversal(TreeNode root) {if (root null) return;if (root.left ! null root.left.left null root.left.right null) {sum root.left.val;}traversal(root.left);traversal(root.right);
}迭代法
// 先序遍历
class Solution {public int sumOfLeftLeaves(TreeNode root) {if (root null) return 0;StackTreeNode stack new Stack ();stack.add(root);int result 0;while (!stack.isEmpty()) {TreeNode node stack.pop();if (node.left ! null node.left.left null node.left.right null) {result node.left.val;}if (node.right ! null) stack.add(node.right);if (node.left ! null) stack.add(node.left);}return result;}
}// 层序遍历
class Solution {public int sumOfLeftLeaves(TreeNode root) {int sum 0;if (root null) return 0;QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {int size queue.size();while (size -- 0) {TreeNode node queue.poll();if (node.left ! null) { // 左节点不为空queue.offer(node.left);if (node.left.left null node.left.right null){ // 左叶子节点sum node.left.val;}}if (node.right ! null) queue.offer(node.right);}}return sum;}
}时长 10min
收获 参数传递
