就时间和空间复杂性而言，哪种方法来镜像树更好

Question

这是我在下面写的两种方法来镜像Java中的树，这两种方法都可以正常工作。 我刚刚学习了时间复杂度，我想知道哪种方法在时间复杂度和空间复杂性方面效果更好。 第一种方法是我自己做的，第二种方法是老师给我的。 这两种方法之间的主要区别在于，在第一种方法中，不会创建新树，而在第二种方法中会创建一个树。 提前感谢！

//way 1
public static TreeNode mirrorImage (TreeNode t) {
    if (t == null)
        return null;
    TreeNode right = t.getRight();
    TreeNode left = t.getLeft();
    t.setLeft(mirrorImage(right));
    t.setRight(mirrorImage(left));
    return t;
}
//way 2
public static TreeNode mirrorImage (TreeNode t) {
    if (t == null)
        return null;
    else
        return new TreeNode (t.getValue(), mirrorImage(t.getRight()), 
           mirrorImage(t.getLeft()));
}

这是 treeNode 类供您帮助:)

class TreeNode {
    private Object value; 
    private TreeNode left, right;
    public TreeNode(Object initValue) { 
        value = initValue; 
        left = null; 
        right = null; 
    }
    public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight) { 
        value = initValue; 
        left = initLeft; 
        right = initRight; 
    }
    public Object getValue() { 
        return value; 
    }
    public TreeNode getLeft()  { 
        return left; 
    }
    public TreeNode getRight()  { 
        return right; 
    }
    public void setValue(Object theNewValue)  { 
        value = theNewValue; 
    }
    public void setLeft(TreeNode theNewLeft)  { 
        left = theNewLeft;
    }
    public void setRight(TreeNode theNewRight) { 
        right = theNewRight;
    }
}

Answer 1

时间复杂度没有差异。其中n是树节点的数量，两种情况下的时间复杂度都是O(n)。你访问每个TreeNode一次。

方式 1 具有空间复杂度O(1)，方式 2 具有空间复杂度O(n)，假设原始树已经存在。如果将原始树的构造计为算法的一部分，则在这两种情况下，空间复杂度都O(n)，如 O(2n) == O(n) 。