一起射福利,久久夜色撩人精品国产,国产性爱在线视频不卡,性一色一乱一肉一情,日韩无码破解,亚洲五月网,揉我胸啊嗯出水了描述,操大B毛片视频

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎知識和業(yè)務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?路徑總和 II，我們先來看題面：

https://leetcode-cn.com/problems/path-sum-ii/

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

題意

給定一個二叉樹和一個目標和，找到所有從根節(jié)點到葉子節(jié)點路徑總和等于給定目標和的路徑。

說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。

樣例

解題

https://www.yuque.com/zhoujx/study/lc112

方法一：深度優(yōu)先搜索

我們可以采用深度優(yōu)先搜索的方式，枚舉每一條從根節(jié)點到葉子節(jié)點的路徑。當我們遍歷到葉子節(jié)點，且此時路徑和恰為目標和時，我們就找到了一條滿足條件的路徑。

class?Solution?{
????List<List> ret = new?LinkedList<List>();
????Deque path = new?LinkedList();

????public?List<List> pathSum(TreeNode root, int sum) {
????????dfs(root, sum);
????????return?ret;
????}

????public?void dfs(TreeNode root, int sum) {
????????if?(root == null) {
????????????return;
????????}
????????path.offerLast(root.val);
????????sum -= root.val;
????????if?(root.left == null?&& root.right == null?&& sum == 0) {
????????????ret.add(new?LinkedList(path));
????????}
????????dfs(root.left, sum);
????????dfs(root.right, sum);
????????path.pollLast();
????}
}

方法二：廣度優(yōu)先搜索

我們也可以采用廣度優(yōu)先搜索的方式，遍歷這棵樹。當我們遍歷到葉子節(jié)點，且此時路徑和恰為目標和時，我們就找到了一條滿足條件的路徑。

為了節(jié)省空間，我們使用哈希表記錄樹中的每一個節(jié)點的父節(jié)點。每次找到一個滿足條件的節(jié)點，我們就從該節(jié)點出發(fā)不斷向父節(jié)點迭代，即可還原出從根節(jié)點到當前節(jié)點的路徑。

class?Solution?{
????List> ret = new?LinkedList>();
????Map map = new?HashMap();

????public?List> pathSum(TreeNode root, int?sum) {
????????if?(root == null) {
????????????return?ret;
????????}

????????Queue queueNode = new?LinkedList();
????????Queue queueSum = new?LinkedList();
????????queueNode.offer(root);
????????queueSum.offer(0);

????????while?(!queueNode.isEmpty()) {
????????????TreeNode node = queueNode.poll();
????????????int?rec = queueSum.poll() + node.val;

????????????if?(node.left == null?&& node.right == null) {
????????????????if?(rec == sum) {
????????????????????getPath(node);
????????????????}
????????????} else?{
????????????????if?(node.left != null) {
????????????????????map.put(node.left, node);
????????????????????queueNode.offer(node.left);
????????????????????queueSum.offer(rec);
????????????????}
????????????????if?(node.right != null) {
????????????????????map.put(node.right, node);
????????????????????queueNode.offer(node.right);
????????????????????queueSum.offer(rec);
????????????????}
????????????}
????????}

????????return?ret;
????}

????public?void?getPath(TreeNode node) {
????????List temp = new?LinkedList();
????????while?(node != null) {
????????????temp.add(node.val);
????????????node = map.get(node);
????????}
????????Collections.reverse(temp);
????????ret.add(new?LinkedList(temp));
????}
}