java - 递归与深度优先搜索

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:

该方法的时间复杂度和空间复杂度是多少？

Answer 1

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

尽管如此:

答案 1:

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

答案 2:

由于您只对每个节点进行一次评估，因此您的时间复杂度为O(n) 其中 n 是树中的节点数。

你的空间复杂度应该类似于O(d)，其中d是树的深度，因为你必须记住Solution(left) 计算解(右)

时