我有一个二叉搜索树,我想找到从根到叶子的最小路径和,下面是我的递归解决方案
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:
该方法的时间复杂度和空间复杂度是多少?
最佳答案
首先,这个问题在codeReview中会更好。或computer science 。不确定是哪一个,但我倾向于使用计算机科学来解决复杂性问题。
尽管如此:
答案 1:
是的,这确实是深度优先,因为您甚至在从右子树开始之前就到达了左子树中的叶子。
答案 2:
由于您只对每个节点进行一次评估,因此您的时间复杂度为
O(n)
其中 n
是树中的节点数。
你的空间复杂度应该类似于O(d)
,其中d
是树的深度,因为你必须记住Solution(left)
计算解(右)
关于java - 递归与深度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36134468/