二叉树的镜像

题目描述

示例

代码

代码1 层次遍历翻转

/*
层次遍历 左右翻转
*/
function Mirror( pRoot ) {
    if(pRoot === null) return null
    
    let q = [] // 使用数组模拟队列
    q.push(pRoot) // 入队
    
    // 开始层次遍历
    while(q.length>0){
        let current = q.shift() // 出队
        
        // 把这一层节点的left和right替换
        
        let tempNode = current.left
        current.left = current.right
        current.right = tempNode
        
        // 开始遍历下一层，把下一层的节点入队
        if(current.left){
            q.push(current.left)
        }
        if(current.right){
            q.push(current.right)
        }
        
    }
    return pRoot
}

代码2 深度优先搜索翻转翻转

/*
深度优先搜索 翻转
log(root.val)
dfs(root.left)
dfs(root.right)
*/
function Mirror( pRoot ) {
    if(!pRoot) return null
    
    let temp = pRoot.left
    pRoot.left = pRoot.right
    pRoot.right = temp
    
    // 因为翻转了 所以换个头。先right再left
    Mirror(pRoot.right)
    Mirror(pRoot.left)
    return pRoot
}

代码3 中序遍历翻转

/*
中序遍历 左根右 翻转
inOrder(root.left)
log(root.val)
inOrder(root.right)
*/
function Mirror( pRoot ) {
    if(!pRoot) return null
    
    Mirror(pRoot.left)
    
    let temp = pRoot.left
    pRoot.left = pRoot.right
    pRoot.right = temp
    
    // 因为已经翻转了，所以把right改为left
    Mirror(pRoot.left)
    return pRoot
}

题目来源

JZ27 二叉树的镜像