我想知道克隆二叉树的代码的时间复杂度是否为 O(n)？
如果是 O(n) 你能解释一下为什么吗？
如果没有，你能建议一种时间复杂度为 O(n) 的方法吗？
public TreeNode cloneTree(TreeNode root) {
if (root == null) return null;
TreeNode newNode = new TreeNode(root.val);
newNode.left = cloneTree(root.left);
newNode.right = cloneTree(root.right);
return newNode;
}
You might think it's O(2n) because of the two recursive child calls, but all tree walking algorithms like this are O(n). Every node of the tree is visited only one time; if you add 10 nodes to the tree, you get 10 more stack frames spawned by the algorithm, which is a linear relationship. Yes, the frame has pre-, in- and post- stages to the child visits, so control does return back to the frame multiple times, but this is normal linear behavior and there's no way to improve the complexity while visiting each node in the tree.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
