给你二叉树的根节点 root
和一个整数目标和 targetSum
,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null) {
return result;
}
path.add(root.val);
backtracking(root, targetSum - root.val);
return result;
}
public void backtracking(TreeNode root, int sum) {
if (sum == 0 && root.left == null && root.right == null) {
result.add(new ArrayList<>(path));
return;
}
if (root.left != null) {
path.add(root.left.val);
sum -= root.left.val;
backtracking(root.left, sum);
sum += root.left.val;
path.remove(path.size() - 1);
}
if (root.right != null) {
path.add(root.right.val);
sum -= root.right.val;
backtracking(root.right, sum);
sum += root.right.val;
path.remove(path.size() - 1);
}
}
}
给你二叉树的根结点 root
,请你将它展开为一个单链表:
TreeNode
,其中 right
子指针指向链表中下一个结点,而左子指针始终为 null
。class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<>();
preorder(root, list);
for (int i = 1; i < list.size(); i++) {
TreeNode pre = list.get(i - 1);
TreeNode cur = list.get(i);
pre.left = null;
pre.right = cur;
}
}
public void preorder(TreeNode root, List<TreeNode> list) {
if (root != null) {
list.add(root);
preorder(root.left, list);
preorder(root.right, list);
}
}
}