LeetCode算法题-Invert Binary Tree

佚名 6年前 (2018-12-07) 算法 902人围观抢沙发百度已收录

这是悦乐书的第194次更新，第199篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第55题（顺位题号是226）。反转二叉树。例如：
输入：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输出：

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

二叉树的任意一个节点进行反转操作时，当前节点还是当前节点，当前节点的左子节点变成右子节点，当前节点的右子节点变成左子节点。也就是下面的三行核心代码：

TreeNode temp = root.left;
root.left = root.right;
root.right = temp;

如果从根节点开始，那么先把根节点的左右子节点互换，然后利用递归，再将已经互换了的左右子节点他们自身的左右子节点进行互换，最后返回root。

public TreeNode invertTree(TreeNode root) {
    if (root == null || (root.left == null && root.right == null)) {
        return root;
    }
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    root.left = invertTree(root.left);
    root.right = invertTree(root.right);
    return root;
}

03 第二种解法

此解法比上面的第一种解法精简了些，直接将上面核心代码进行套用，将root的左子节点取出存入tmp，再将root的左子节点指向递归后的root的右子节点，再将root的右子节点指向递归后的tmp，最后返回root即可。

public TreeNode invertTree2(TreeNode root) {
    if (root == null || (root.left == null && root.right == null)) {
        return root;
    }
    TreeNode tmp = root.left;
    root.left = invertTree2(root.right);
    root.right = invertTree2(tmp);
    return root;
}

04 第三种解法

利用队列，借助其先进先出的特性。在进行循环进队列、出队列的操作时，核心代码还是最开始那三行代码，进行左右子节点互换。

public TreeNode invertTree3(TreeNode root) {
    TreeNode r = root;
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    if (root != null) {
        q.add(root);        
    }
    while (!q.isEmpty()) {
        TreeNode curr = q.remove();
        TreeNode temp = curr.left;
        curr.left = curr.right;
        curr.right = temp;
        if (curr.left != null) {
            q.add(curr.left);
        }
        if (curr.right != null) {
            q.add(curr.right);
        }
    }
    return r;
}