05翻转二叉树

一、题目

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：


输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：


输入：root = [2,1,3]
输出：[2,3,1]

示例 3：


输入：root = []
输出：[]

提示：

树中节点数目范围在 [0, 100] 内

100 <= Node.val <= 100

二、思路

注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果

三、ts实现

递归实现

前序


const swap = (root: TreeNode) => {
    let temp: TreeNode;
    temp = root.left;
    root.left = root.right;
    root.right = temp;
}

function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    swap(root);
    invertTree(root.left);
    invertTree(root.right);
    return root;
};

后序


const swap = (root: TreeNode) => {
    let temp: TreeNode;
    temp = root.left;
    root.left = root.right;
    root.right = temp;
}

function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    invertTree(root.left);
    invertTree(root.right);
    swap(root);
    return root;
};

中序


const swap = (root: TreeNode) => {
    let temp: TreeNode;
    temp = root.left;
    root.left = root.right;
    root.right = temp;
}

function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    invertTree(root.left);
    swap(root);
    invertTree(root.left); // 这里是left是因为 swap(root);交换了两个子树，right侧转过去了
    return root;
};

迭代实现

前序


function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    const stack: TreeNode[] = [];

    stack.push(root);

    while(stack.length) {
        const cur = stack.pop();

        let tempNode: TreeNode;

        tempNode = cur.left;
        cur.left = cur.right;
        cur.right = tempNode;

        if (cur.left) stack.push(cur.left);
        if (cur.right) stack.push(cur.right);
    }

    return root;
};

后序


function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    const stack: TreeNode[] = [];
    stack.push(root);

    while(stack.length) {
        const cur = stack.pop();

        if (cur.left) stack.push(cur.left);
        if (cur.right) stack.push(cur.right);

        let tempNode: TreeNode;
        tempNode = cur.left;
        cur.left = cur.right;
        cur.right = tempNode;
    }

    return root;
};

中序


function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    const stack: TreeNode[] = [];
    stack.push(root);

    while(stack.length) {
        const cur = stack.pop();

        if (cur.left) stack.push(cur.left);
        let tempNode: TreeNode;
        tempNode = cur.left;
        cur.left = cur.right;
        cur.right = tempNode;
        if (cur.left) stack.push(cur.left); // 这里跟递归的原因是一致的
    }

    return root;
};

层序遍历


function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    const queue: TreeNode[] = [];
    queue.push(root);
    while(queue.length) {
        const size = queue.length;

        for(let i = 0; i < size; i++) {
            let tempNode;
            const cur = queue.shift();
            tempNode = cur.left;
            cur.left = cur.right;
            cur.right = tempNode;
            if (cur.left) queue.push(cur.left);
            if (cur.right) queue.push(cur.right);
        }
    }

    return root;
};