LeetCode-226. 翻转二叉树

问题地址

LeetCode每日一题/2020-09-16

LeetCode226. 翻转二叉树

问题描述

规则

• 翻转一棵二叉树。

示例

• 示例

输入：
    4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：
     4
   /   \
  7     2
 / \   / \
9   6 3   1

备注

• 这个问题是受到 Max Howell 的 原问题 启发的 ：
  > 谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

解析

解题思路

• 使用递归交换左右子树
• root为空，结束递归

数据操作分析

编码实现

public class LeetCode0226_InvertBinaryTree {
    public TreeNode invertTree(TreeNode root) {
        TreeNode res = recurisve(root);
        return res;
    }

    private TreeNode recurisve(TreeNode root) {
        if (root == null) return root;
        if (root.left == null && root.right == null) return root;
        TreeNode tmp = root.left;
        root.left = root.right;
        recurisve(root.left);
        root.right = tmp;
        recurisve(root.right);
        return root;
    }
}

官方解法

方法一：递归

思路：

• 这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子结点先开始翻转。如果当前遍历到的节点 \textit{root} 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 \textit{root} 为根节点的整棵子树的翻转。

算法：

复杂度分析

1. 时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。
   2.空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(\log N)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

编码实现

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

精彩评论

跳转地址1：「226. 翻转二叉树：【递归法】【迭代法】详细讲解！

思路

• 写递归算法的时候，要想一想是采用前中后序哪种遍历方式。如果对二叉树递归的方式还不熟，可以看这篇题解 彻底吃透二叉树的前中后序递归法和迭代法！！
• 我们先看看递归算法，对于二叉树的递归方式有三种前中后序，这道题用前序方便一点。通过动画来看一下翻转的过程:
  

递归三部曲

• 确定递归函数的参数和返回值
  • 参数就是要传入节点的指针，不需要其他参数了，返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以就返回一个指针。

TreeNode* invertTree(TreeNode* root)

• 确定终止条件
  • 当前节点为空的时候，就返回

if (root == NULL) return root;

• 确定单层递归的逻辑
  • 因为是先序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。

swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);

编码实现

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

迭代法

leetcode-master 中给出了 前中后序迭代法统一的模板，使用前序遍历，只需要改动一行就可以了，代码在下面已经给出。

前序遍历

• 递归法

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

• 迭代法

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            swap(node->left, node->right);
            if(node->left) st.push(node->left);
            if(node->right) st.push(node->right);
        }
        return root;
    }
};

• 迭代法前序遍历模板，模板地址：leetcode-master

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 添加右节点
                if (node->left) st.push(node->left);    // 添加左节点
                st.push(node);                          // 添加中节点
                st.push(NULL);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                swap(node->left, node->right);          // 节点处理逻辑
            }
        }
        return root;
    }
};