人妻系列在线播放,久久青青草av夜夜

寫在前

本部分題目，討論自頂向下的情況，就是從某一個節(jié)點(diǎn)(不一定是根節(jié)點(diǎn))，從上向下尋找路徑，到某一個節(jié)點(diǎn)(不一定是葉節(jié)點(diǎn))結(jié)束，而繼續(xù)細(xì)分的話還可以分成一般路徑與給定和的路徑。
注意：這類題通常用深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)解決，BFS較DFS繁瑣，這里為了簡潔只展現(xiàn)DFS代碼

1.二叉樹的所有路徑（257-易）

題目描述：給定一個二叉樹，返回所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑。

示例：

輸入:

   1
 /   \
2     3
 \
  5

輸出: ["1->2->5", "1->3"]

解釋: 所有根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑為: 1->2->5, 1->3

思路：遞歸實(shí)現(xiàn)

如果root不為空，我們才進(jìn)行拼接！
判斷是否到達(dá)葉子節(jié)點(diǎn)。如果到達(dá)，加入集合返回結(jié)果；否則，拼接箭頭，遞歸左右子樹。

代碼實(shí)現(xiàn)：

public List<String> binaryTreePaths(TreeNode root) {
    List<String> ans = new ArrayList<>(); 
    if (root == null) {
        return ans;
    }
    dfs(root, "", ans);
    return ans;
}

private void dfs(TreeNode root, String path, List<String> ans) {
    if (root == null) {
        return;
    }
    StringBuilder sb = new StringBuilder(path);
    sb.append(String.valueOf(root.val));
    if (root.left == null && root.right == null) {
        ans.add(sb.toString());
    } else {
        sb.append("->");
        dfs(root.left, sb.toString(), ans);
        dfs(root.right, sb.toString(), ans);
    }
}

2.求和路徑（面試題04.12）

題目描述：給定一棵二叉樹，其中每個節(jié)點(diǎn)都含有一個整數(shù)數(shù)值(該值或正或負(fù))。設(shè)計一個算法，打印節(jié)點(diǎn)數(shù)值總和等于某個給定值的所有路徑的數(shù)量。注意，路徑不一定非得從二叉樹的根節(jié)點(diǎn)或葉節(jié)點(diǎn)開始或結(jié)束，但是其方向必須向下(只能從父節(jié)點(diǎn)指向子節(jié)點(diǎn)方向)。

示例：

給定如下二叉樹，以及目標(biāo)和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

返回:3
解釋：和為 22 的路徑有：[5,4,11,2], [5,8,4,5], [4,11,7]

思路：遞歸實(shí)現(xiàn)

本題關(guān)鍵是路徑的起止點(diǎn)不確定，所以我們要在主函數(shù)遞歸左右子節(jié)點(diǎn)（累加結(jié)果）
我們維護(hù)一個變量記錄結(jié)果，即當(dāng)root.val == sum時我們獲得一個結(jié)果，累積左右子節(jié)點(diǎn)。

代碼實(shí)現(xiàn)：

public int pathSum(TreeNode root, int sum) {
    if (root == null) {
        return 0;
    }
    return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}

private int dfs(TreeNode root, int sum) {
    if (root == null) {
        return 0;
    }
    int ans = sum == root.val ? 1 : 0;
    sum -= root.val;
    return dfs(root.left, sum) + dfs(root.right, sum) + ans;
}

3.路徑總和（112-易）

題目描述：給你二叉樹的根節(jié)點(diǎn) root 和一個表示目標(biāo)和的整數(shù) targetSum ，判斷該樹中是否存在根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和 targetSum 。

示例：

輸入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
輸出：true

思路：遞歸實(shí)現(xiàn)

終止條件，如果當(dāng)前節(jié)點(diǎn)為空，返回false
到達(dá)葉子節(jié)點(diǎn)，且sum = root.val
遞歸的左右子節(jié)點(diǎn)（注意更新sum值，即減去root.val）

代碼實(shí)現(xiàn)：

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) {
        return false;
    }
    sum -= root.val;
    if (root.left == null && root.right == null && sum == 0) {
        return true;
    } 
    return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}

4.路徑總和II（113-中）

題目描述：本題在上題基礎(chǔ)上（從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑和等于給定值），要求找出這些路徑！

示例：

輸入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
輸出：[[5,4,11,2],[5,8,4,5]]

思路：遞歸實(shí)現(xiàn)，注意本題與257不同的是需要回溯。

我們先加入路徑，不滿足需要從隊(duì)列中刪除，所以需要實(shí)現(xiàn)一個雙端隊(duì)列。
注意找到一個結(jié)果也需要繼續(xù)進(jìn)行回溯。

代碼實(shí)現(xiàn)：

List<List<Integer>> ans = new LinkedList<>();
Deque<Integer> path = new LinkedList<>();

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return ans;
    }
    dfs(root, targetSum);
    return ans;
}

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

拓展（T437）：這里路徑不限制從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，但是方向一定是從上到下的。

注意：區(qū)分開始節(jié)點(diǎn)（主遞歸函數(shù)）和結(jié)束節(jié)點(diǎn)（判斷結(jié)束標(biāo)志）！

代碼實(shí)現(xiàn)：

public int pathSum(TreeNode root, int sum) {
    if (root == null) {
        return 0;
    }
    return pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}

private int pathSumStartWithRoot(TreeNode root, int sum) {
    if (root == null) {
        return 0;
    }
    int ans = 0;
    sum -= root.val;
    if (sum == 0) {
        ans++;
    }
    ans += pathSumStartWithRoot(root.left, sum) + pathSumStartWithRoot(root.right, sum);
    return ans;
}

5.從葉子節(jié)點(diǎn)開始的最小字符串（988-中）

題目描述：給定一顆根結(jié)點(diǎn)為 root 的二叉樹，樹中的每一個結(jié)點(diǎn)都有一個從 0 到 25 的值，分別代表字母 'a' 到 'z'：值 0 代表 'a'，值 1 代表 'b'，依此類推。

找出按字典序最小的字符串，該字符串從這棵樹的一個葉結(jié)點(diǎn)開始，到根結(jié)點(diǎn)結(jié)束。

（小貼士：字符串中任何較短的前綴在字典序上都是較小的：例如，在字典序上 "ab" 比 "aba" 要小。葉結(jié)點(diǎn)是指沒有子結(jié)點(diǎn)的結(jié)點(diǎn)。）

示例：

輸入：[0,1,2,3,4,3,4]
輸出："dba"

思路：遞歸實(shí)現(xiàn)，需要進(jìn)行回溯，一些必要的函數(shù)：

直接使用StringBuilder的reverse()方法進(jìn)行反轉(zhuǎn)，反轉(zhuǎn)兩次是為了繼續(xù)進(jìn)行拼接。
使用compareTo()比較兩個字符串的字典序（本質(zhì)是比較ascii值）
使用deleteCharAt(待刪除的索引)進(jìn)行回溯

注意：我們是更新獲取最小的字典序，所以我們初始值應(yīng)該大于'z'的ascii值

代碼實(shí)現(xiàn)：

String ans = "~";
public String smallestFromLeaf(TreeNode root) {
    if (root == null) {
        return ans;
    }
    dfs(root, new StringBuilder());
    return ans;
}

private void dfs(TreeNode root,  StringBuilder sb) {
    if (root == null) {
        return;
    }
    sb.append((char)(root.val + 'a'));

    if (root.left == null && root.right == null) {
        sb.reverse();
        String tmp = sb.toString();
        sb.reverse();

        if (tmp.compareTo(ans) < 0) {
            ans = tmp;
        }
    }

    dfs(root.left, sb);
    dfs(root.right, sb);
    sb.deleteCharAt(sb.length() - 1);
}

6.根節(jié)點(diǎn)到葉子節(jié)點(diǎn)數(shù)字之和（129-中）

題目描述：給你一個二叉樹的根節(jié)點(diǎn) root ，樹中每個節(jié)點(diǎn)都存放有一個 0 到 9 之間的數(shù)字。
每條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑都代表一個數(shù)字：

例如，從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑 1 -> 2 -> 3 表示數(shù)字 123 。計算從根節(jié)點(diǎn)到葉節(jié)點(diǎn)生成的所有數(shù)字之和。

示例：

輸入：root = [1,2,3]
輸出：25
解釋：
從根到葉子節(jié)點(diǎn)路徑 1->2 代表數(shù)字 12
從根到葉子節(jié)點(diǎn)路徑 1->3 代表數(shù)字 13
因此，數(shù)字總和 = 12 + 13 = 25

思路：遞歸實(shí)現(xiàn)，遞歸所有的路徑（根節(jié)點(diǎn)到葉子節(jié)點(diǎn)），進(jìn)行累加。

定義一個變量記錄自上向下的路徑和。
當(dāng)?shù)竭_(dá)葉子節(jié)點(diǎn)，找到一條路徑和。
遞歸的尋找左右子節(jié)點(diǎn)。

代碼實(shí)現(xiàn)：

public int sumNumbers(TreeNode root) {
    return dfs(root, 0);
}

private int dfs(TreeNode root, int pathSum) {
    if (root == null) {
        return 0;
    }
    pathSum = pathSum * 10 + root.val;
    if (root.left == null && root.right == null) {
        return pathSum;
    }
    return dfs(root.left, pathSum) + dfs(root.right, pathSum);
}

注意點(diǎn)

如果是找路徑和等于給定target的路徑的，那么可以不用新增一個臨時變量cursum來判斷當(dāng)前路徑和，只需要用給定和target減去節(jié)點(diǎn)值，最終結(jié)束條件判斷target==0即可。
是否要回溯：二叉樹的問題大部分是不需要回溯的，原因如下：二叉樹的遞歸部分：dfs(root->left),dfs(root->right)已經(jīng)把可能的路徑窮盡了,因此到任意葉節(jié)點(diǎn)的路徑只可能有一條，絕對不可能出現(xiàn)另外的路徑也到這個滿足條件的葉節(jié)點(diǎn)的;但是對路徑有限制，則需要使用回溯！如T4和T5；

二維數(shù)組(例如迷宮問題)的DFS,for循環(huán)向四個方向查找每次只能朝向一個方向，并沒有窮盡路徑，因此某一個滿足條件的點(diǎn)可能是有多條路徑到該點(diǎn)的；

并且visited數(shù)組標(biāo)記已經(jīng)走過的路徑是會受到另外路徑是否訪問的影響，這時候必須回溯
找到路徑后是否要return:取決于題目是否要求找到葉節(jié)點(diǎn)滿足條件的路徑,如果必須到葉節(jié)點(diǎn),那么就要return（也可以不return）; 但如果是到任意節(jié)點(diǎn)都可以，那么必不能return,因?yàn)檫@條路徑下面還可能有更深的路徑滿足條件，還要在此基礎(chǔ)上繼續(xù)遞歸
是否要雙重遞歸(即調(diào)用根節(jié)點(diǎn)的dfs函數(shù)后，繼續(xù)調(diào)用根左右節(jié)點(diǎn)的pathsum函數(shù))：看題目要不要求從根節(jié)點(diǎn)開始的，還是從任意節(jié)點(diǎn)開始

本部分題目，非自頂向下：就是從任意節(jié)點(diǎn)到任意節(jié)點(diǎn)的路徑，不需要自頂向下

7.二叉樹最大路徑和（124-難）

題目描述：路徑被定義為一條從樹中任意節(jié)點(diǎn)出發(fā)，沿父節(jié)點(diǎn)-子節(jié)點(diǎn)連接，達(dá)到任意節(jié)點(diǎn)的序列。同一個節(jié)點(diǎn)在一條路徑序列中至多出現(xiàn)一次 。該路徑至少包含一個節(jié)點(diǎn)，且不一定經(jīng)過根節(jié)點(diǎn)。

路徑和是路徑中各節(jié)點(diǎn)值的總和。給你一個二叉樹的根節(jié)點(diǎn) root ，返回其最大路徑和。

示例：

輸入：root = [-10,9,20,null,null,15,7]
輸出：42
解釋：最優(yōu)路徑是 15 -> 20 -> 7 ，路徑和為 15 + 20 + 7 = 42

思路：遞歸實(shí)現(xiàn)，遞歸函數(shù)的關(guān)鍵寫好遞歸處理的邏輯，怎么處理當(dāng)前子樹，需要返回什么，設(shè)置遞歸出口。關(guān)鍵是正確定義遞歸函數(shù)。

遞歸函數(shù)：計算當(dāng)前節(jié)點(diǎn)為父親節(jié)點(diǎn)提供的貢獻(xiàn)（即當(dāng)前節(jié)點(diǎn)到根節(jié)點(diǎn)的最大路徑）。
遞歸的計算左右子節(jié)點(diǎn)的最大貢獻(xiàn)值，邏輯：貢獻(xiàn)值大于0，才會選取對應(yīng)的節(jié)點(diǎn)最大貢獻(xiàn)值
更新最大路徑和（當(dāng)前節(jié)點(diǎn)值和左右子節(jié)點(diǎn)最大貢獻(xiàn)值）

特別注意：dfs函數(shù)中定義的是一個節(jié)點(diǎn)能貢獻(xiàn)的最大值（計算該節(jié)點(diǎn)到根節(jié)點(diǎn)的最大路徑），而我們統(tǒng)計結(jié)果時更新的二叉樹中任意兩點(diǎn)的最大路徑（可能是多個節(jié)點(diǎn)到這個根節(jié)點(diǎn)的組合）！

代碼實(shí)現(xiàn)：

private int ans = 0;

public int longestUnivaluePath(TreeNode root) {
    dfs(root);
    return ans;
}
private int dfs(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int l = dfs(root.left);
    int r = dfs(root.right);
    int left = root.left != null && root.val == root.left.val ? l : 0;
    int right = root.right != null && root.val == root.right.val ? r : 0;

    ans = Math.max(ans, left + right);
    return Math.max(left, right) + 1;
}

8.最長同值路徑（687-中）

題目描述：給定一個二叉樹，找到最長的路徑，這個路徑中的每個節(jié)點(diǎn)具有相同值。這條路徑可以經(jīng)過也可以不經(jīng)過根節(jié)點(diǎn)。

注意：兩個節(jié)點(diǎn)之間的路徑長度由它們之間的邊數(shù)表示。

示例：

思路：遞歸實(shí)現(xiàn)，思想與上題基本相似。

遞歸函數(shù)：當(dāng)前節(jié)點(diǎn)到根節(jié)點(diǎn)的最長同值路徑
遞歸左右子樹的最長同值路徑；邏輯：出現(xiàn)同值，更新路徑左右路徑，否則為0
更新最長同值路徑

代碼實(shí)現(xiàn)：

public int pathSum(TreeNode root, int sum) {
    if (root == null) {
        return 0;
    }
    return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}

private int dfs(TreeNode root, int sum) {
    if (root == null) {
        return 0;
    }
    int ans = sum == root.val ? 1 : 0;
    sum -= root.val;
    return dfs(root.left, sum) + dfs(root.right, sum) + ans;
}

9.二叉樹的直徑（543-易）

題目描述：給定一棵二叉樹，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結(jié)點(diǎn)路徑長度中的最大值。這條路徑可能穿過也可能不穿過根結(jié)點(diǎn)。

注意：兩個節(jié)點(diǎn)之間的路徑長度由它們之間的邊數(shù)表示。

示例：

給定二叉樹

          1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的長度是路徑 [4,2,1,3] 或者 [5,2,1,3]。

思路：遞歸實(shí)現(xiàn)，遞歸實(shí)現(xiàn)，思想與上題基本相似，還是區(qū)分遞歸函數(shù)和最終結(jié)果的區(qū)別。

代碼實(shí)現(xiàn)：

private int max = 0;

public int diameterOfBinaryTree(TreeNode root) {
    dfs(root);
    return max;
}
private int dfs(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = dfs(root.left);
    int right = dfs(root.right);

    max = Math.max(max, left + right); 
    return Math.max(left, right) + 1;
}

附（特殊）:所有距離為k的節(jié)點(diǎn)（863-中）

題目描述：給定一個二叉樹（具有根結(jié)點(diǎn) root），一個目標(biāo)結(jié)點(diǎn) target ，和一個整數(shù)值 K 。

返回到目標(biāo)結(jié)點(diǎn) target 距離為 K 的所有結(jié)點(diǎn)的值的列表。答案可以以任何順序返回。

示例：

輸入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
輸出：[7,4,1]
解釋：
所求結(jié)點(diǎn)為與目標(biāo)結(jié)點(diǎn)（值為 5）距離為 2 的結(jié)點(diǎn)，
值分別為 7，4，以及 1

思路：本題搜索的大體思路可以按照圖的bfs，我們需要給所有節(jié)點(diǎn)添加一個指向父節(jié)點(diǎn)的引用（這樣就知道了距離該節(jié)點(diǎn)1距離的所有節(jié)點(diǎn)），進(jìn)而找到距離target節(jié)點(diǎn)為k的所有節(jié)點(diǎn)。

用map集合構(gòu)建每個節(jié)點(diǎn)的父節(jié)點(diǎn)，即建立當(dāng)前節(jié)點(diǎn)到父節(jié)點(diǎn)的引用（構(gòu)建圖）
用hashset記錄節(jié)點(diǎn)是否被訪問過
我們可以看成以當(dāng)前節(jié)點(diǎn)為中心的輻射（是一種廣度搜索的思想），完成一層之后k--。

代碼實(shí)現(xiàn)：

private Map<TreeNode, TreeNode> parents;
private Set<TreeNode> isVisited;
private List<Integer> ans;

public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
    parents = new HashMap<>();
    getParents(root, null);
    
    isVisited = new HashSet<>();
    ans = new ArrayList<>();

    Deque<TreeNode> queue = new LinkedList<>();
    queue.add(target);

    while (!queue.isEmpty()) {
        if (k-- == 0) {
            while (!queue.isEmpty()) {
                ans.add(queue.poll().val);
            }
            break;
        }

        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            TreeNode node = queue.poll();
            isVisited.add(node);
            if (node.left != null && !isVisited.contains(node.left)) {
                queue.add(node.left);
            }
            if (node.right != null && !isVisited.contains(node.right)) {
                queue.add(node.right);
            }

            TreeNode p = parents.get(node);
            if (p != null && !isVisited.contains(p)) {
                queue.add(p);
            }
        }
    }
    return ans;
}

private void getParents(TreeNode root, TreeNode parent) {
    if (root == null) {
        return;
    }
    parents.put(root, parent);
    getParents(root.left, root);
    getParents(root.right, root);
}

注意點(diǎn)

left,right代表的含義要根據(jù)題目所求設(shè)置，比如最長路徑、最大路徑和等等
全局變量res的初值設(shè)置是0還是INT_MIN要看題目節(jié)點(diǎn)是否存在負(fù)值,如果存在就用INT_MIN，否則就是0
注意兩點(diǎn)之間路徑為1，因此一個點(diǎn)是不能構(gòu)成路徑的

巨人的肩膀：

https://leetcode-cn.com/problems/smallest-string-starting-from-leaf/solution/yi-pian-wen-zhang-jie-jue-suo-you-er-cha-10sk/
b

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

二叉樹的路徑解析（任意兩點(diǎn)/自頂向下）

二叉樹的路徑解析（任意兩點(diǎn)/自頂向下）

寫在前

1.二叉樹的所有路徑（257-易）

2.求和路徑（面試題04.12）

3.路徑總和（112-易）

4.路徑總和II（113-中）

5.從葉子節(jié)點(diǎn)開始的最小字符串（988-中）

6.根節(jié)點(diǎn)到葉子節(jié)點(diǎn)數(shù)字之和（129-中）

注意點(diǎn)

7.二叉樹最大路徑和（124-難）

8.最長同值路徑（687-中）

9.二叉樹的直徑（543-易）

附（特殊）:所有距離為k的節(jié)點(diǎn)（863-中）

注意點(diǎn)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

二叉樹的路徑解析（任意兩點(diǎn)/自頂向下）

寫在前

1.二叉樹的所有路徑（257-易）

2.求和路徑（面試題04.12）

3.路徑總和（112-易）

4.路徑總和II（113-中）

5.從葉子節(jié)點(diǎn)開始的最小字符串（988-中）

6.根節(jié)點(diǎn)到葉子節(jié)點(diǎn)數(shù)字之和（129-中）

注意點(diǎn)

7.二叉樹最大路徑和（124-難）

8.最長同值路徑（687-中）

9.二叉樹的直徑（543-易）

附（特殊）:所有距離為k的節(jié)點(diǎn)（863-中）

注意點(diǎn)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av