递归与深度优先搜索

Question

我有一个二叉搜索树，我想找到从根到叶的最小路径和，下面是我的递归解决方案

public int Solution(TreeNode root) {
    if (root == null)   return 0;
    if (root.left != null && root.right == null)
        return Solution(root.left) + root.val;
    if (root.left == null && root.right != null)
        return Solution(root.right) + root.val;
    return Math.min(Solution(root.left), Solution(root.right)) + root.val;
}

问题 #1：

这个解决方案是深度优先搜索，因为它首先到达左子树的最深处（我假设）。

问题 #2：

这个方法的时间复杂度和space复杂度是多少？

Answer 1

首先，这个问题在 codeReview or computer science 中会更好。不确定哪个，但我倾向于使用计算机科学来解决复杂性问题。

尽管如此：

答案 1：

是的，它确实是深度优先，因为你甚至在从右子树开始之前就到达了左子树中的叶子。

答案 2：

因为你只对每个节点求值一次，所以你的时间复杂度是 O(n) 其中 n 是树中的节点数。

您的 Space 复杂度应该类似于 O(d)，其中 d 是树的深度，因为您在计算 [=15= 时必须记住 Solution(left) ]

递归与深度优先搜索

Recursion vs Depth first search

java

recursion

time-complexity

depth-first-search

问题 #1：

问题 #2：

答案 1：

答案 2：