算法-递归-对称二叉树

蔚落 2023-01-05 15:28 176阅读 0赞

# 算法-递归-对称二叉树 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/symmetric-tree/

## 1.2 题目描述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]

# 2.1 双指针+递归 #

## 2.1 解题思路 ##

1.  根据对称树的特点，我们用两个指针分别往左子节点和右子节点递归查询
2.  每次查询时比较他们是否都为空，
3.  如果都不为空就比较是否值相等
4.  如果值相等，就继续检查左节点的左节点和右节点的右节点、左节点的右节点和右节点的左节点
5.  只要都相同就说明对称，否则不对称

## 2.2 代码 ##

## 2.3 时间复杂度 ##

![在这里插入图片描述][20210113115250251.png]  
O(N)

## 2.4 空间复杂度 ##

O(N)

# 3 迭代+BFS #

## 3.1 解题思路 ##

1.  我们使用一个队列，根据对称树的特点，每次分别将左子节点和右子节点放入队列完成初始化
2.  每次从队列中取出两个元素作对比，
3.  对比时，分别判断空值、不为空值时各种情况
4.  如果发现不等，直接返回；否则继续按左节点的左节点、右节点的右节点、左节点的右节点、右节点的左节点的顺序加入到Queue中

## 3.2 代码 ##

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        public boolean isSymmetric(TreeNode root) { 
            if(root == null){ 
                return true;
            }
            // return check(root.left, root.right);
            return check2(root);
        }
    
        private boolean check2(TreeNode root){ 
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root.left);
            queue.add(root.right);
            while(!queue.isEmpty()){ 
                TreeNode left = queue.poll();
                TreeNode right = queue.poll();
                if(left == null && right == null){ 
                    continue;
                }
    
                if((left == null || right == null) || left.val != right.val){ 
                    return false;
                }
    
                queue.add(left.left);
                queue.add(right.right);
    
                queue.add(left.right);
                queue.add(right.left);
            }
            
            return true;
        }
    }

## 3.3 时间复杂度 ##

O(N)

## 3.4 空间复杂度 ##

O(N)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: /images/20221119/848538c3406d445e91c68ad92e22c729.png
[20210113115250251.png]: https://img-blog.csdnimg.cn/20210113115250251.png