平衡二叉樹
題目鏈接
思路
遞歸判斷左右子樹深度面褐，如果差值為>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;
}
二叉樹所有路徑
題目鏈接
思路
遞歸回溯咱士，每一次遞歸記錄當(dāng)前遍歷的節(jié)點路徑，遞歸出來后需要回溯進入下一次遞歸
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));// 記錄最后一個節(jié)點
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
思路
理解左葉子定義，遞歸實現(xiàn)
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);
}