leetcode 110. 平衡二叉树
题目描述
给定一个二叉树，判断它是否是 平衡二叉树
示例
输入：root = [3,9,20,null,null,15,7]
输出：true
解决思路
根据平衡二叉树的定义，左右子树高度差小于等于1，且左右子树也都是平衡的。进行自上而下递归查询
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return isBalanced(root.left) && isBalanced(root.right) && Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1 ? true : false;
}
public int getDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
}
}
自下向上递归
从下往上求高度，如果左右子树有一个求的高度为 -1，或者高度差大于 1，则直接返回 -1，说明是不平衡的，否则能求出该二叉树的高度。
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) >= 0;
}
public int height(TreeNode root) {
if (root == null) return 0;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
leetcode 257. 二叉树的所有路径
题目描述
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]
解决思路
递归，每次搜索如果是叶子结点，则插入到路径中（相当于递归终点），否则继续遍历左右子树
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
// 按照前序遍历的顺序进行，如果是叶子结点则加入路径中
constructPaths(root, "", paths);
return paths;
}
public void constructPaths(TreeNode root, String path, List<String> paths) {
if (root != null) {
StringBuilder sb = new StringBuilder(path);
// 当前节点插入
sb.append(Integer.toString(root.val));
if (root.left == null && root.right == null) { // 当前是叶子结点，添加到路径中
paths.add(sb.toString());
} else {
sb.append("->");
// 继续遍历
constructPaths(root.left, sb.toString(), paths);
constructPaths(root.right, sb.toString(), paths);
}
}
}
}
leetcode 404. 左叶子之和
题目描述
给定二叉树的根节点 root ，返回所有左叶子之和。
示例
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
解决思路
递归遍历，和是左子树结果加上右子树结果，如果当前节点的左孩子是叶子结点，则加上它的值
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
int sum = sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
if (root.left != null && root.left.left == null && root.left.right == null) {
sum += root.left.val;
}
return sum;
}
}
leetcode 513. 找树左下角的值
题目描述
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
解决思路
要寻找最底层最左边的节点，实则就是找层序遍历的最后一层的第一个节点
class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> que = new LinkedList<>();
if (root != null) que.offer(root);
int res = 0;
while (!que.isEmpty()) {
res = que.peek().val;
int len = que.size();
while (len-- > 0) {
TreeNode node = que.poll();
if (node.left != null) que.offer(node.left);
if (node.right != null) que.offer(node.right);
}
}
return res;
}
}
评论