平衡二叉树
题目链接
思路
递归判断左右子树深度，如果差值为>1即是不平衡的
public boolean isBalanced(TreeNode root) {
return getDepth(root) != -1;
}
private int getDepth(TreeNode node) {
if(node == null) {
return 0;
}
int leftHeight = getDepth(node.left);
if(leftHeight == -1) {
return -1;
}
int rightHeight = getDepth(node.right);
if(rightHeight == -1) {
return -1;
}
if(Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
二叉树所有路径
题目链接
思路
递归回溯，每一次递归记录当前遍历的节点路径，递归出来后需要回溯进入下一次递归
public List<String> binaryTreePaths(TreeNode root) {
List<String> list = new ArrayList();
List<Integer> path = new ArrayList();
visitPaths(root, path, list);
return list;
}
private void visitPaths(TreeNode node, List<Integer> path, List<String> res) {
path.add(node.val);
if(node.left == null && node.right == null) {
// 输出
StringBuilder sb = new StringBuilder();// StringBuilder用来拼接字符串，速度更快
for (int i = 0; i < path.size() - 1; i++) {
sb.append(path.get(i)).append("->");
}
sb.append(path.get(path.size() - 1));// 记录最后一个节点
res.add(sb.toString());// 收集一个路径
return;
}
if(node.left != null) {
visitPaths(node.left, path, res);
path.remove(path.size() - 1);
}
if(node.right != null) {
visitPaths(node.right, path, res);
path.remove(path.size() - 1);
}
}
左叶子之和
题目链接
https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html
思路
理解左叶子定义，递归实现
public int sumOfLeftLeaves(TreeNode root) {
if(root == null) {
return 0;
}
int val = 0;
if(root.left != null && root.left.left == null && root.left.right == null) {
val = root.left.val;
}
return val + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}