LeetCode-257. 二叉树的所有路径

问题地址

LeetCode每日一题/2020-09-04

LeetCode257. 二叉树的所有路径

问题描述

规则

• 给定一个二叉树，返回所有从根节点到叶子节点的路径。
• 说明: 叶子节点是指没有子节点的节点。

示例1

输入:
   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

解析

解题思路

• 首先想到的方法是深度优先搜索。树节点分两种，叶子节点、非叶子节点，根据不同的节点类型，采用不同的处理方法：
  • 如果当前节点是叶子节点：
    • 将当前节点添加到当前路径末尾；
    • 将得到的一条从根节点到叶子节点的路径，加入到答案；
  • 如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。
  • 如此，当遍历完整棵二叉树以后我们就得到了所有从根节点到叶子节点的路径。当然，深度优先搜索也可以使用非递归的方式实现，这里不再赘述。

复杂度分析

1. 时间复杂度，O(N^2)，其中 N 表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对 path 变量进行拷贝构造，时间代价为 O(N)，故时间复杂度为 O(N^2)。
2. 空间复杂度，O(N^2)，其中 N 表示节点数目。除答案数组外我们需要考虑递归调用的栈空间。在最坏情况下，当二叉树中每个节点只有一个孩子节点时，即整棵二叉树呈一个链状，此时递归的层数为 N，此时每一层的 path 变量的空间代价的总和为 O(\sum_{i = 1}^{N} i) = O(N^2) 空间复杂度为 O(N^2)。最好情况下，当二叉树为平衡二叉树时，它的高度为 \log N，此时空间复杂度为 O((\log {N})^2)。

数据操作分析

• 遍历树，根据节点类型采取不同的处理方法；

编码实现

/**
 * LeetCode0257
 */
public class LeetCode0257_BinaryTreePaths {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        explore(root, "", result);
        return result;
    }

    private void explore(TreeNode root, String path, List<String> result) {
        if (root != null) {
            StringBuilder sb = new StringBuilder(path);
            sb.append(root.val);
            if (root.right == null && root.left == null) {
                result.add(sb.toString());
            } else {
                sb.append("->");
                explore(root.left, sb.toString(), result);
                explore(root.right, sb.toString(), result);
            }
        }

    }
}

官方解法

广度优先搜索

思路：

• 我们也可以用广度优先搜索来实现。我们维护一个队列，存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中，我们取出队列中的首节点，如果它是叶子节点，则将它对应的路径加入到答案中。如果它不是叶子节点，则将它的所有孩子节点加入到队列的末尾。当队列为空时广度优先搜索结束，我们即能得到答案。

复杂度分析：

1. 时间复杂度，O(N^2)。
2. 空间复杂度，O(N^2)，其中 N 表示节点数目。在最坏情况下，队列中会存在 N 个节点，保存字符串的队列中每个节点的最大长度为 N，故空间复杂度为 O(N^2)。

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        if (root == null) {
            return paths;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<String> pathQueue = new LinkedList<String>();

        nodeQueue.offer(root);
        pathQueue.offer(Integer.toString(root.val));

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll(); 
            String path = pathQueue.poll();

            if (node.left == null && node.right == null) {
                paths.add(path);
            } else {
                if (node.left != null) {
                    nodeQueue.offer(node.left);
                    pathQueue.offer(new StringBuffer(path).append("->").append(node.left.val).toString());
                }

                if (node.right != null) {
                    nodeQueue.offer(node.right);
                    pathQueue.offer(new StringBuffer(path).append("->").append(node.right.val).toString());
                }
            }
        }
        return paths;
    }
}