/*class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return TreeNode类
*/
/**
* 方法一:递归
* 时间复杂度:O(n),访问二叉树所有节点各一次
* 空间复杂度:O(n),递归栈最大值
*/
export function Mirror(pRoot: TreeNode): TreeNode {
if (pRoot == null) return null
const left: TreeNode = Mirror(pRoot.left)
const right: TreeNode = Mirror(pRoot.right)
pRoot.left = right
pRoot.right = left
return pRoot
}
/**
* 方法二:栈(拓展思路)
* 时间复杂度:O(n),访问二叉树所有节点各一次
* 空间复杂度:O(n),最坏的情况下,递归栈最大值
*/
// export function Mirror(pRoot: TreeNode): TreeNode {
// if (pRoot == null) return null
// const stack: TreeNode[] = []
// stack.push(pRoot)
// while (stack.length) {
// const curNode = stack.pop()
// if (curNode.left != null) stack.push(curNode.left)
// if (curNode.right != null) stack.push(curNode.right)
// // 交换
// const tempNode = curNode.left
// curNode.left = curNode.right
// curNode.right = tempNode
// }
// return pRoot
// }