我最近在利用业余时间解算法问题,为明年夏季实习面试做准备。目前我正在解决与树有关的问题,我发现对于大多数问题来说,实际编码并不困难,但是我很难理解这些问题的复杂性。我正在解决的一个问题是二叉树的前序遍历,我已经实现了递归和迭代两种方法。然而,迭代方案要慢得多,并且我不明白为什么?以下是我的两种解决方案:
迭代:
public List<Integer> preorder(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return ans;
stack.push(root);
while(!stack.isEmpty()) {
TreeNode node = stack.pop();
ans.add(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
{
return ans;
}
递归:
public list<Integer> preorder(TreeNode root) {
List<Integer> ans = new ArrayList<>();
dfs(root, ans);
return ans;
}
public void dfs (TreeNode root, List<Integer> ans) {
if (root == null) return;
ans.add(root.val);
dfs(root.left);
dfs(node.right)
}
据我所见,递归解决方案每次调用有两个分支,如果树是平衡的,则深度为O(log n),但最坏情况是O(n),因此时间复杂度将为O(2^n)。我的看法可能完全错误。迭代解决方案具有恒定的推入和弹出时间,因此我的初步直觉是它的时间复杂度为O(n)。如果这些是情况,我无法想象指数解决方案如何运行更快。如果有人能帮助我理解这类问题的复杂性,那将非常感激。