617. 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-binary-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。o-binary-trees/)
解题思路及方法
从根节点开始合并，递归方法比较简单，就是比较左右子树是否为空的时候比较麻烦。
说一点，在调用递归的时候，要判断传入结点是否为空，不然在调用时会出现空指针的报错。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) return null;
TreeNode root = new TreeNode();
// 合并根结点
if (root1 != null && root2 != null) {
root.val = root1.val + root2.val;
} else {
root.val = root1 == null ? root2.val : root1.val;
}
// 递归左右子树
root.left = mergeTrees(root1 == null ? null : root1.left, root2 == null ? null : root2.left);
root.right = mergeTrees(root1 == null ? null : root1.right, root2 == null ? null : root2.right);
return root;
}
}
结果如下
404. 左叶子之和
计算给定二叉树的所有左叶子之和。
示例：
3
/ \
9 20
/ \
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-left-leaves
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路及方法
这个就很简单了，从根节点开始，判断是否为左叶子，然后用全局变量记录和，接着递归。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int sum = 0;
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
// 判断是否左叶子
if (root.left != null && root.left.left == null && root.left.right == null) {
sum += root.left.val;
}
// 递归寻找左右子树的左叶子
sumOfLeftLeaves(root.left);
sumOfLeftLeaves(root.right);
return sum;
}
}
结果如下
653. 两数之和 IV - 输入 BST
解题思路及方法
跟 1. 两数之和这道题的思路一样，用一个list记录已经出现的节点的值，然后递归，当list中存在k-root.val的时候，说明满足题意，return true，否则return false。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> memo = new ArrayList<>();
public boolean findTarget(TreeNode root, int k) {
if (root == null) return false;
if (memo.contains(k - root.val)) {
return true;
} else {
// 备忘录添加值
memo.add(root.val);
}
return findTarget(root.left, k) || findTarget(root.right, k);
}
}
结果如下
872. 叶子相似的树
解题思路及方法
这道题我感觉做麻烦了，代码还可以修改。
单独写一个方法用来寻找叶节点，用一个全局变量list按先序遍历的顺序记录下来，然后获得两棵树的叶节点序列，判断是否相等。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> leafList = new ArrayList<>();
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
List<Integer> r1List = findLeaf(root1);
this.leafList = new ArrayList<>();
List<Integer> r2List = findLeaf(root2);
if (r1List.equals(r2List)) return true;
return false;
}
public List<Integer> findLeaf(TreeNode root) {
if (root == null) return null;
// 判断是否叶结点
if (root.left == null && root.right == null) {
leafList.add(root.val);
}
// 递归左右子树
findLeaf(root.left);
findLeaf(root.right);
return leafList;
}
}
结果如下
