代码随想录刷题|LeetCode 226.翻转二叉树 101.对称二叉树

简介: 代码随想录刷题|LeetCode 226.翻转二叉树 101.对称二叉树

226.翻转二叉树

题目链接:力扣

思路

拿到翻转二叉树的时候看起来挺复杂的,但是仔细看就能看出,翻转二叉树其实就是将每个节点的左右节点进行交换(这是完成这道题的关键)


       既然我们要交换每个节点的左右子节点,就要先对每个节点进行访问,然后再对每个节点的左右节点进行处理,这里跟为两步进行:访问节点和处理节点


       处理节点简单,就是将节点的两个左右节点进行交换就可以了

       访问节点就需要根据题目选择合适的遍历方法


       递归法:使用递归法要做好递归的三部曲

       迭代法(深度优先):

       迭代法(层序遍历):只是在层序遍历的基础上添加了对节点的处理


       做完这道题目的感觉:遍历二叉树的方式就那几种。首先你要审题,看题目是要干什么,然后根据题目原则合适的访问节点的方法(遍历二叉树),因为二叉树的节点可能会因为处理节点发生改变,好的遍历方式是关键。然后在访问节点的过程中对节点进行处理就可以了


翻转二叉树

递归法

       第一步:确定递归函数的参数和返回值

       第二步:确定终止条件

       第三步:确定单层的递归逻辑

/**
*采用前序遍历
*/
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}
/**
*采用后序遍历
*/
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        invertTree(root.left);
        invertTree(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }
}

迭代法

深度优先遍历(迭代法)

       采用前序遍历的迭代法,其实迭代节点的方法都一样,就是看访问到节点之后怎么进行处理

// 采用前序遍历的迭代法
class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 创建模拟栈
        Deque<TreeNode> stack = new ArrayDeque<>();
        // 先将根节点压栈
        stack.addFirst(root);
        while (!stack.isEmpty()) {
            // 先弹栈
            TreeNode node = stack.removeFirst();
            // 弹出来的元素交换左右子节点
            reverseNode(node);
            // 将右子树压栈
            if (node.right != null) {
                stack.push(node.right);
            }
            // 将左子树压栈
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return root;
    }
    public void reverseNode (TreeNode node) {
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}


层序遍历(迭代法)

       只是再层序遍历的基础山添加了对节点的处理

/**
采用层序遍历
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            while (len-- > 0) {
                // 先让队出队
                TreeNode node = queue.poll();
                // 交换其左右节点
                TreeNode temp = node.right;
                node.right = node.left;
                node.left = temp;
                // 将该节点的左右子节点入队
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }      
        }
        return root;
    }
}

101.对称二叉树

题目链接:力扣

思路

       一开始做的时候想的是判断每个节点的左右节点如果是对称的就可以,这样的思路是错误的

04178982bedb42789369d79d5b6b0d6c.png



   比如这个对称二叉树,2下面的3和4是不对称的,但这是个对称二叉树


       所以判断一个二叉树是不是对称二叉树,不应该是判断每个节点的左右节点是否相等,而是应该判断每个节点的左子树和右子树是否互为翻转二叉树


       接下来我们要确定采取哪种遍历方式了:这道题目只能采用后序遍历,也就是说对中间节点的处理(判断左右两边是否互为翻转),要从二叉树的最底层往上进行判断,所以需要对根节点的左子树采取左右中的遍历方式,同时对右子树采取右左中的遍历方式,才可以逐一进行比较


39d45513e9a74b92a82671d2589b357e.png



对称二叉树

递归法


因为要比较的是根节点的两个子树是否是相互翻转的,进而判断这个树是不是对称树,所以要比较的是两棵树,所以递归函数的参数是两棵树


       这道题目的终止条件比较多,要把所有情况都涵盖了


       比较外侧是否相等

       比较内侧是否相等

       收获结果

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left,root.right);
    }
    // 确定递归函数的参数和返回值
    public boolean compare(TreeNode left,TreeNode right) {
        if (left == null && right != null) {return false;}
        if (left != null && right == null) {return false;}
        if (left == null && right == null) {return true;}
        if (left.val != right.val) {return false;}
        // 比较外侧
        boolean outside = compare(left.left,right.right); // 左子树的左  右子树的右
        // 比较内侧
        boolean inside = compare(left.right,right.left);  // 左子树的右  右子树的左
        // 判断是否互为翻转
        return outside && inside; // 根节点  中
    }
}

迭代法

       递归法本质上是从最下面往最上面进行检测

       迭代法本质上是从最上面往最下面进行检测


       需要注意的是,这个队列是可以添加空节点的,所以java中实现队列的时候要用LinkedList来实现,LinkedList是允许添加null元素的,其他实现类是不可以的


       注意添加的顺序,一定是内侧和内侧一起添加,外侧和外侧一起添加

class Solution {
    public boolean isSymmetric(TreeNode root) {
        // 创建一个队列,用来存放内外侧的值,进行比较
        // 因为在下面添加节点的时候要添加空节点,所以要用LinkedList实现
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode leftnode = queue.poll();
            TreeNode rightnode = queue.poll();
            if (leftnode == null && rightnode == null) {
                continue;
            }
            if (leftnode == null || rightnode == null || leftnode.val != rightnode.val) {
                return false;
            }
            // 能来到这里的都是相等的
            // 再分别加入上两个节点的外侧和内侧节点
            // 加入外侧节点
            queue.offer(leftnode.left);
            queue.offer(rightnode.right);
            // 加入内侧节点
            queue.offer(leftnode.right);
            queue.offer(rightnode.left);
        }
        return true;
    }
}
相关文章
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
25 1
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
20 0
|
2月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
15 0
|
2月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
17 0
|
2月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
20 0
|
2月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
19 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
58 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2
|
3月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口