Go Java演演算法之二元樹的所有路徑範例詳解

2022-08-18 14:02:10

二元樹的所有路徑

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

葉子節點是指沒有子節點的節點。

範例 1：

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

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

範例 2：

輸入：root = [1]

輸出：["1"]

提示：

樹中節點的數目在範圍 [1, 100] 內

-100 <= Node.val <= 100

方法一：深度優先遍歷搜尋（Java）

最直觀的方法是使用深度優先搜尋。在深度優先搜尋遍歷二元樹時，我們需要考慮當前的節點以及它的孩子節點。

如果當前節點不是葉子節點，則在當前的路徑末尾新增該節點，並繼續遞迴遍歷該節點的每一個孩子節點。

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

遞迴二步曲：

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

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

(2) 確定終止條件。

對於二元樹的所有路徑中的每條路徑，當遍歷到葉子節點的時候為當前路徑的結束。並且將當前路徑加入結果集。

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) {  // 當前節點是葉子節點
                paths.add(pathSB.toString());  // 把路徑加入到答案中
            } else {
                pathSB.append("->");  // 當前節點不是葉子節點，繼續遞迴遍歷
                constructPaths(root.left, pathSB.toString(), paths);
                constructPaths(root.right, pathSB.toString(), paths);
            }
        }
    }
}

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

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

方法二：廣度優先遍歷（Go）

我們也可以用廣度優先搜尋來實現。

我們維護一個佇列，儲存節點以及根到該節點的路徑。一開始這個佇列裡只有根節點。
在每一步迭代中，我們取出佇列中的首節點
如果它是葉子節點，則將它對應的路徑加入到答案中。如果它不是葉子節點，則將它的所有孩子節點加入到佇列的末尾。
當佇列為空時廣度優先搜尋結束

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
}