LeetCode-二叉树的所有路径(每日一题)

题目描述

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   1
 /   \
2     3
 \
  5

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

解法

1. DFS

思路：根据官方题解写出。当遇到叶节点时，将字符串添加到结果中；否则对左右子节点进行深度优先搜索（每一个节点都传入一个新生成的字符串👀）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.List;
import java.util.ArrayList;
class Solution {
    private List<String> ans;

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

    private void dfs(TreeNode node, String str) {
        // 下面没有对左右节点是否为空的判断，需要在这里判断。
        if (node != null) {
            // 添加节点到字符串
            StringBuilder sb = new StringBuilder(str);
            sb.append(Integer.toString(node.val));
            // 遇到叶节点
            if (node.left == null && node.right == null) {
                ans.add(sb.toString());
            } else {
                sb.append("->");
                // 左节点
                dfs(node.left, sb.toString());
                // 右节点
                dfs(node.right, sb.toString());
            }
        }
    }
}

时间复杂度为$O(n^2)$ DFS会对n个节点进行一次访问，每次访问时对字符串进行拷贝构造，时间代价为$O(n)$，一共为$O(n^2)$
空间复杂度为$O(n^2)$ 递归栈的层数+字符串占用的变量

2. DFS+回溯

思路：可能是昨天N皇后的后遗症😭，我一拿到题的思路就是深度优先搜索+回溯。使用一个path栈来储存一条路径，当到达叶节点时就将path添加到结果中；否则向左右子节点搜索，走完后回退。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

class Solution {
    private List<String> ans;

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

    private void dfs(TreeNode node, Stack<Integer> path) {
        path.push(node.val);
        if (node.left == null && node.right == null) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < path.size() - 1; i++) {
                sb.append(path.get(i) + "->");
            }
            sb.append(path.get(path.size() - 1));
            ans.add(sb.toString());
        } else {
            if (node.left != null) {
                dfs(node.left, path);
                // 退回
                path.pop();
            }
            if (node.right != null) {
                dfs(node.right, path);
                // 退回
                path.pop();
            }
        }
    }
}