34题目描述:
给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
解析:
1.初始化参数,结果列表res ,路径列表path,最后返回 res 即可。
2.backTrack函数:
递推参数:当前节点root,当前目标值target
终止条件:若节点root为空,则直接返回
3.递推工作:
路径更新:
将当前节点值 root.val 加入路径 path
目标值更新:target -= node.val
路径记录:当root为叶节点且路径和等于目标值,则将此路径path加入res
先序遍历:递归左/右子节点
路径恢复:向上回溯前,需要将当前节点从路径path中删除,即执行path.remove(path.size() - 1);
Java:
public List<List<Integer>> pathSum(TreeNode root, int target) {
backTrack(root, target, new ArrayList<>());
return res;
}
private List<List<Integer>> res = new ArrayList<>();
private void backTrack(TreeNode node, int target, List<Integer> path) {
if(node == null) {
return;
}
path.add(node.val);
target -= node.val;
if(target == 0 && node.left == null && node.right == null) {
res.add(new ArrayList<>(path));
} else {
backTrack(node.left, target, path);
backTrack(node.right, target, path);
}
path.remove(path.size() - 1);
}
JavaScript:
var pathSum = function(root, target) {
const res = [];
const path = [];
root && backTrack(root, target, path, 0, res);
return res;
};
function backTrack(node, target, path, sum, res) {
path.push(node.val);
sum += node.val;
if(!node.left && !node.right && sum === target) {
res.push([...path]);
}
node.left && backTrack(node.left, target, path, sum, res);
node.right && backTrack(node.right, target, path, sum, res);
path.pop();
}
36题目描述:
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
解析:
1.如果根节点为null,则返回null
2.递归根节点
3.然后使头尾节点相互连接,最后返回头节点
4.递归法中序遍历
(1)终止条件:当节点curr为空,代表越过叶节点,直接返回
(2)递归左子树,即dfs(curr.left)
(3)构建链表
当prev为空时,代表正在访问链表头节点,记为head;
当prev不为空时,修改双向节点引用,即prev.right = curr,curr.left = prev;
保存curr,更新prev = curr,即节点curr是后继节点的prev;
(4)递归右子树,即dfs(curr.right)
Java:
private Node prev, head;
public Node treeToDoublyList(Node root) {
if(root == null) {
return null;
}
dfs(root);
head.left = prev;
prev.right = head;
return head;
}
private void dfs(Node curr) {
if(curr == null) {
return;
}
dfs(curr.left);
curr.left = prev;
if(prev == null) {
head = curr;
} else {
prev.right = curr;
}
prev = curr;
dfs(curr.right);
}
JavaScript:
var treeToDoublyList = function(root) {
if(root === null) {
return null;
}
let head = null;
let prev = null;
dfs(root);
head.left = prev;
prev.right = head;
return head;
function dfs(curr) {
if(curr === null) {
return;
}
dfs(curr.left);
curr.left = prev;
if(prev === null) {
head = curr;
} else {
prev.right = curr;
}
prev = curr;
dfs(curr.right);
}
};