java - 反转二叉树时的性能差异

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;
    }
}

Answer 1

看到真实的数字是值得的。但是如果我们谈论相当大的树，那可能是因为缓存:
在第一个解决方案中，您读取 root.left 和 root.right，然后进行反转，最后您再次操作 root.left 和 root.right。
在第二个解决方案中，您交换 root.left 和 root.right，然后立即进行反转。因此，您至少为每个节点避免了一次缓存未命中。实际上，即使指令代码也可能更短一条指令，因为它可能会重用已读取的变量。