二叉树的左右子树交换

[sisterAn]

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

leetcode

[liuzb30]

var invertTree = function(root) {
    if(root==null) return root
    const queue = [root]
    while(queue.length){
        const cur = queue.shift();
        // 交换左右节点
        [cur.left,cur.right] = [cur.right,cur.left]
        cur.left && (queue.push(cur.left))
        cur.right && (queue.push(cur.right))
    }
    return root
}

[sisterAn]

遍历+交换左右子树

解题思路： 从根节点开始依次遍历每个节点，然后交换左右子树既可

const invertTree = (root) => {
    if(!root) return null
    // 先翻转当前节点的左右子树
    const temp = root.left
    root.left = root.right
    root.right = temp
    // 然后遍历左子树
    invertTree(root.left)
    // 再遍历右子树
    invertTree(root.right)
    return root
}

这里采用的是前序遍历，也可以是后序遍历或层序遍历