java这些镜像树的方法中，哪一种在时间和空间复杂度方面更好

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)。你每次都会去一次

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