关注Java领域相关技术 记录有趣的事情

LeetCode-226. 翻转二叉树

US-B.Ralph
US-B.Ralph
2020-09-16

问题地址

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;
    }
};
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;
    }
};
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

9 + 3 =