- 617 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
//递归法
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) return t2;
if (t2 == null) return t1;
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}
// 循环法
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) return t2;
Stack<TreeNode[]> sta = new Stack<>();
sta.push(new TreeNode[] {t1, t2});
while (!sta.isEmpty()) {
TreeNode[] curr = sta.pop();
if (curr[0] == null || curr[1] == null)
continue;
curr[0].val += curr[1].val;
if (curr[0].left == null) {
curr[0].left = curr[1].left;
} else {
sta.push(new TreeNode[] {curr[0].left, curr[1].left});
}
if (curr[0].right == null) {
curr[0].right = curr[1].right;
} else {
sta.push(new TreeNode[] {curr[0].right, curr[1].right});
}
}
return t1;
}
- 修剪二叉搜索树
给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
\\递归
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) return null;
if (root.val > R) return trimBST(root.left, L, R);
if (root.val < L) return trimBST(root.right, L, R);
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
- 二叉树的层平均值
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
//depth first
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Integer> count = new ArrayList<>();
List<Double> res = new ArrayList<>();
average(root, 0, count, res);
for (int i=0; i < count.size(); i++) {
res.set(i, res.get(i) / count.get(i));
}
return res;
}
public void average(TreeNode t, int i, List<Integer> count, List<Double> sum) {
if (t == null) return ;
if (i < count.size()) {
count.set(i, count.get(i) + 1);
sum.set(i, sum.get(i) + t.val);
}
else {
count.add(1);
sum.add(1.0 * t.val);
}
average(t.left, i+1, count, sum);
average(t.right, i+1, count, sum);
}
}
// Breadth First Search
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
long sum=0, count=0;
Queue<TreeNode> tmp = new LinkedList<>();
while (!queue.isEmpty()) {
TreeNode n = queue.remove();
count++;
sum+=n.val;
if (n.left != null) {
tmp.add(n.left);
}
if (n.right != null) {
tmp.add(n.right);
}
}
queue = tmp;
res.add(sum*1.0 / count);
}
return res;
}
