題目

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

解法思路（一）

關(guān)于遞歸問(wèn)題的思考順序

• 先一頭扎進(jìn)遞歸的最底層，就最底層的情況進(jìn)行思考；
• 然后從最底層往上走一層，對(duì)這一層的情況進(jìn)行思考；
• 再往上走一層，就是遞歸的一般情況；

二叉樹的所有路徑解法描述

• 如果到了最底，二叉樹為空了，返回給上一層一個(gè)空線性表；
• 如果在倒數(shù)第二層，二叉樹為葉子節(jié)點(diǎn)，返回包含葉子節(jié)點(diǎn)的線性表到上一層；
• 如果二叉樹或者有左孩子，或者有右孩子，或者既有左孩子又有右孩子，遞歸的去其左孩子和右孩子為根的二叉樹中找路徑；
• 左孩子為根的二叉樹的所有路徑以線性表的形式返回，右孩子也是一樣；
• 把當(dāng)前根節(jié)點(diǎn)加到兩個(gè)線性表中包含的所有路徑的前面；
• 將兩個(gè)線性表中的所有路徑合在一個(gè)線性表中返回給上一層；

解法實(shí)現(xiàn)（一）

時(shí)間復(fù)雜度

• 好像挺慢的，具體我也算不出來(lái)，感覺O(h^2)吧；

空間復(fù)雜度

• O(h) 吧感覺；

關(guān)鍵字

二叉樹的所有路徑 二叉樹 遞歸 遞歸的返回值

實(shí)現(xiàn)細(xì)節(jié)

• 兩個(gè)線性表合并的時(shí)候，誰(shuí)合并誰(shuí)好像是有區(qū)別的；

package leetcode._257;

import java.util.LinkedList;
import java.util.List;

public class Solution257_1 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public List<String> binaryTreePaths(TreeNode root) {

        if (root == null) {
            return new LinkedList<String>();
        }

        if (root.left == null && root.right == null) {
            List<String> path = new LinkedList<>();
            path.add(String.valueOf(root.val));
            return path;
        }

        List<String> leftPath = binaryTreePaths(root.left);
        List<String> rightPath = binaryTreePaths(root.right);

        for(int i = 0; i < leftPath.size(); i++) {
            String s = leftPath.remove(i);
            s = root.val + "->" + s;
            leftPath.add(i, s);
        }

        for(int i = 0; i < rightPath.size(); i++) {
            String s = rightPath.remove(i);
            s = root.val + "->" + s;
            rightPath.add(i, s);
        }

        for(String p : rightPath)
            leftPath.add(p);

        return leftPath;
    }

}

解法實(shí)現(xiàn)（二）

時(shí)間復(fù)雜度

• O(n)，n為樹中的節(jié)點(diǎn)個(gè)數(shù)；

空間復(fù)雜度

• O(h)，h為樹的高度；

關(guān)鍵字

二叉樹的所有路徑 二叉樹 遞歸 遞歸的返回值

實(shí)現(xiàn)細(xì)節(jié)

• LinkedList 換成了 ArrayList；
• 字符串拼接變成了 StringBuilder；
• 避免了 leftPaht 和 rightPath 的合并；

package leetcode._257;

import java.util.ArrayList;
import java.util.List;

public class Solution257_2 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public List<String> binaryTreePaths(TreeNode root) {

        ArrayList<String> res = new ArrayList<String>();

        if(root == null)
            return res;

        if(root.left == null && root.right == null){
            res.add(Integer.toString(root.val));
            return res;
        }

        List<String> leftPaths = binaryTreePaths(root.left);
        for(String s: leftPaths){
            StringBuilder sb = new StringBuilder(Integer.toString(root.val));
            sb.append("->");
            sb.append(s);
            res.add(sb.toString());
        }

        List<String> rightPaths = binaryTreePaths(root.right);
        for(String s: rightPaths) {
            StringBuilder sb = new StringBuilder(Integer.toString(root.val));
            sb.append("->");
            sb.append(s);
            res.add(sb.toString());
        }

        return res;
    }

}

返回 LeetCode [Java] 目錄