二叉樹的所有路徑(所有從根節點到葉子節點的路徑)-257

題目描述

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

解題思路

這道題我們採用二叉樹里的前序遍歷方式，我們要遍歷所有到葉子節點的路徑，我們採用復用的思想，就是讓這裡的幾個數據結構我們可以重覆使用，但是重覆使用也就帶來數據不一致的情況，我們用一個temp集合來存儲遍歷路上遇到的元素，但是這裡的元素我們肯定是要變化的，你遍歷了左葉子節點，那下次你遍歷右葉子節點的時候你就要把左葉子節點的值給從我們這個temp集合中去除，所以這裡就體現了回溯的思想，一層一層的往上回溯，直到最後回溯的只剩下了根節點，然後再同樣的方法去遍歷根節點的右子樹。

代碼實例

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        travel(root, temp, result);
        return result;
    }

    public void travel(TreeNode root, List<Integer> temp, List<String> result) {

        temp.add(root.val);
        if (root.left == null && root.right == null) {
            result.add(zhuanhua(temp));
            return;
        }

        if (root.left != null) {
            travel(root.left, temp, result);
            //這裡就是回溯的思想，先讓底下的節點一層一層遍歷然後回溯去除相應的值，再到這裡的根節點就只剩下了根節點，然後就可以去遍歷右子樹了
            temp.remove(temp.size()- 1);
        }
        
        if (root.right != null) {
            travel(root.right, temp, result);
            temp.remove(temp.size()- 1);
        }
    }
    
    public String zhuanhua(List<Integer> num) {
        String sl = "";
        for (int i = 0; i < num.size(); i++) {
            if (i != num.size() - 1) {
                sl += (num.get(i) + "->");
            } else {
                sl += num.get(i);
            }
        }
        return sl;
    }

}