对二叉树进行反求时的性能差异

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

值得看看真实的数字。但如果我们讨论相当大的树，可能是因为缓存:
第一个解是根。左和根。对，然后进行反转，最后再一次操作根结点。Left and root.right.
在第二个解中，你交换根。左和根。对，然后马上做反转。这样就可以避免每个节点至少一次cache-miss。实际上，即使是指令代码也可以缩短一条指令，因为它可以重用已经读取的变量。