反转二叉树的性能差异

Question

现在我有两个解决方案。但是我不明白为什么第一个方案比第二个方案更快。

第一个方案：

public class Solution {
  public TreeNode invertTree(TreeNode root) {
        if(root == null)
            return root;

        if(root.left==null && root.right==null)
            return root;

        TreeNode temp = null;
        root.left = invertTree(root.left);
        root.right =invertTree(root.right);
        temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }
}

第二种解决方案

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null)
            return null;

        if (root.left == null && root.right == null)
            return root;

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

- Jiaming Li

---

这是一个有趣的问题！您能提供实际的时间测量数据，并且发布您测量性能的方法学吗？ - Ben M.

我猜这可能与invertTree的排列有关。对于编译器来说，直接分配可能比更新现有引用更快。 - Sh4d0wsPlyr

@Sh4d0wsPlyr：不，这跟这个毫无关系。这一次不是这个问题。 - Makoto

Answer 1

如果我们谈论相当大的树，看到实际数字是值得的。但这可能是因为缓存的原因：
在第一个解决方案中，您需要读取root.left和root.right，然后执行反转，并且最后再次操作root.left和root.right。
在第二个解决方案中，您需要交换root.left和root.right，然后立即进行反转。因此，您可以避免每个节点至少一个缓存未命中。实际上，指令代码甚至可能比较短，因为它可能重复使用已经读取的变量。

- Zbynek Vyskovsky - kvr000