gt;> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
if(root == null){
return result;
}
find(root, result, temp, targetSum);
return result;
}
public void find(TreeNode root, List<List<Integer>> result, List<Integer> temp, int targetSum){
temp.add(root.val);
if(root.left == null && root.right == null){
int sum = 0;
for(int i = 0; i < temp.size(); i++){
sum += temp.get(i);
}
if(sum == targetSum){
result.add(new ArrayList<Integer>(temp));
}
}
if(root.left != null){
find(root.left, result, temp, targetSum);
temp.remove(temp.size() - 1);
}
if(root.right != null){
find(root.right, result, temp, targetSum);
temp.remove(temp.size() - 1);
}
}
}
106、从中序与后序遍历序列构造二叉树
class Solution {
public Map<Integer, Integer> map;
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i], i);
}
return find(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
public TreeNode find(int[] inorder, int inbegin, int inend, int[] postorder, int pobegin, int poend){
if(inbegin >= inend || pobegin >= poend){
return null;
}
int temp = map.get(postorder[poend - 1]);
int len = temp - inbegin;
TreeNode root = new TreeNode(inorder[temp]);
root.left = find(inorder, inbegin, temp, postorder, pobegin, pobegin + len);
root.right = find(inorder, temp + 1, inend, postorder, pobegin + len, poend - 1);
return root;
}
}
105、从前序与中序遍历序列构造二叉树
class Solution {
public Map<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i], i);
}
return find(inorder, 0, inorder.length, preorder, 0, preorder.length);
}
public TreeNode find(int[] inorder, int inbegin, int inend, int[] preorder, int prbegin, int prend){
if(inbegin >= inend || prbegin >= prend){
return null;
}
int temp = map.get(preorder[prbegin]);
int len = temp - inbegin;
TreeNode root = new TreeNode(inorder[temp]);
root.left = find(inorder, inbegin, temp, preorder, prbegin + 1, prbegin + len + 1);
root.right = find(inorder, temp + 1, inend, preorder, prbegin + len + 1, prend);
return root;
}
}
654、最大二叉树
class Solution {
public Map<Integer, Integer> map;
public TreeNode constructMaximumBinaryTree(int[] nums) {
map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
map.put(nums[i], i);
}
return binaryTree(nums, 0, nums.length - 1);
}
public TreeNode binaryTree(int[] nums, int left, int right){
int max = -1;
for(int i = left; i <= right; i++){
max = max > nums[i] ? max : nums[i];
}
if(max == -1){
return null;
}else{
int index = map.get(max);
TreeNode root = new TreeNode(max);
root.left = binaryTree(nums, left, index - 1);
root.right = binaryTree(nums, index + 1, right);
return root;
}
}
}
617、合并二叉树
/**
* 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 result = new TreeNode();
public TreeNode mergeTrees(TreeNode root1, Tre