Go Java算法之二叉樹的所有路徑示例詳解

更新時間：2022年08月18日 09:16:02 作者：黃丫丫

這篇文章主要為大家介紹了Go Java算法之二叉樹的所有路徑示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

二叉樹的所有路徑

給你一個二叉樹的根節(jié)點 root ，按任意順序，返回所有從根節(jié)點到葉子節(jié)點的路徑。

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

示例 1：

輸入：root = [1,2,3,null,5]

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

示例 2：

輸入：root = [1]

輸出：["1"]

提示：

樹中節(jié)點的數(shù)目在范圍 [1, 100] 內(nèi)

-100 <= Node.val <= 100

方法一：深度優(yōu)先遍歷搜索（Java）

最直觀的方法是使用深度優(yōu)先搜索。在深度優(yōu)先搜索遍歷二叉樹時，我們需要考慮當前的節(jié)點以及它的孩子節(jié)點。

如果當前節(jié)點不是葉子節(jié)點，則在當前的路徑末尾添加該節(jié)點，并繼續(xù)遞歸遍歷該節(jié)點的每一個孩子節(jié)點。

如果當前節(jié)點是葉子節(jié)點，則在當前路徑末尾添加該節(jié)點后我們就得到了一條從根節(jié)點到葉子節(jié)點的路徑，將該路徑加入到答案即可。

遞歸二步曲：

(1) 找出重復的子問題。

前序遍歷的順序是：根節(jié)點、左子樹、右子樹。
在本題同樣也是這個順序：將根節(jié)點加入路徑，遞歸左子樹，遞歸右子樹。
對于左子樹和右子樹來說，也都是同樣的操作。

(2) 確定終止條件。

對于二叉樹的所有路徑中的每條路徑，當遍歷到葉子節(jié)點的時候為當前路徑的結束。并且將當前路徑加入結果集。

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        constructPaths(root, "", paths);
        return paths;
    }
    public void constructPaths(TreeNode root, String path, List<String> paths) {
        if (root != null) {
            StringBuffer pathSB = new StringBuffer(path);
            pathSB.append(Integer.toString(root.val));
            if (root.left == null && root.right == null) {  // 當前節(jié)點是葉子節(jié)點
                paths.add(pathSB.toString());  // 把路徑加入到答案中
            } else {
                pathSB.append("->");  // 當前節(jié)點不是葉子節(jié)點，繼續(xù)遞歸遍歷
                constructPaths(root.left, pathSB.toString(), paths);
                constructPaths(root.right, pathSB.toString(), paths);
            }
        }
    }
}

時間復雜度：O（N^2）

空間復雜度：O（N^2）

方法二：廣度優(yōu)先遍歷（Go）

我們也可以用廣度優(yōu)先搜索來實現(xiàn)。

我們維護一個隊列，存儲節(jié)點以及根到該節(jié)點的路徑。一開始這個隊列里只有根節(jié)點。
在每一步迭代中，我們?nèi)〕鲫犃兄械氖坠?jié)點
如果它是葉子節(jié)點，則將它對應的路徑加入到答案中。如果它不是葉子節(jié)點，則將它的所有孩子節(jié)點加入到隊列的末尾。
當隊列為空時廣度優(yōu)先搜索結束

func binaryTreePaths(root *TreeNode) []string {
    paths := []string{}
    if root == nil {
        return paths
    }
    nodeQueue := []*TreeNode{}
    pathQueue := []string{}
    nodeQueue = append(nodeQueue, root)
    pathQueue = append(pathQueue, strconv.Itoa(root.Val))
    for i := 0; i < len(nodeQueue); i++ {
        node, path := nodeQueue[i], pathQueue[i]
        if node.Left == nil && node.Right == nil {
            paths = append(paths, path)
            continue
        }
        if node.Left != nil {
            nodeQueue = append(nodeQueue, node.Left)
            pathQueue = append(pathQueue, path + "->" + strconv.Itoa(node.Left.Val))
        }
        if node.Right != nil {
            nodeQueue = append(nodeQueue, node.Right)
            pathQueue = append(pathQueue, path + "->" + strconv.Itoa(node.Right.Val))
        }
    }
    return paths
}

時間復雜度：O（N^2）

空間復雜度：O（N^2）

以上就是Go Java算法之二叉樹的所有路徑示例詳解的詳細內(nèi)容，更多關于Go Java算法二叉樹所有路徑的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: