LeetCode_二叉树_简单_101. 对称二叉树

港控/mmm° 2023-10-06 22:42 68阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个二叉树的根节点 root ， 检查它是否轴对称。

**示例 1：**  
![在这里插入图片描述][dd34bbc519cd419c82b0759264cafddc.png]  
输入：root = \[1,2,2,3,4,4,3\]  
输出：true

**示例 2：**  
![在这里插入图片描述][3704be26e35b4a1db45338926f5011eb.png]  
输入：root = \[1,2,2,null,3,null,3\]  
输出：false

**提示：**  
树中节点数目在范围 \[1, 1000\] 内  
\-100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/symmetric-tree

## 2.思路 ##

（1）递归

（2）迭代

## 3.代码实现（Java） ##

//思路1————递归
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            if (root == null) {
        
                return true;
            } else {
        
                //根节点不为 null，检查其左右子树是否对称
                return checkSymmetric(root.left, root.right);
            }
        }
    
        public boolean checkSymmetric(TreeNode left, TreeNode right) {
        
            if (left == null || right == null) {
        
                return left == right;
            }
            if (left.val != right.val) {
        
                return false;
            }
            return checkSymmetric(left.left, right.right) && checkSymmetric(left.right, right.left);
        }
    }

//思路2————迭代
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
    	public boolean isSymmetric(TreeNode root) {
        
    		if (root == null || (root.left == null && root.right == null)) {
        
    			return true;
    		}
    		//用队列保存节点
    		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    		//将根节点的左右孩子放到队列中
    		queue.add(root.left);
    		queue.add(root.right);
    		while (queue.size() > 0) {
        
    			//从队列中取出两个节点，再比较这两个节点
    			TreeNode left = queue.removeFirst();
    			TreeNode right = queue.removeFirst();
    			//如果两个节点都为空就继续循环，两者有一个为空就返回 false
    			if (left == null && right == null) {
        
    					continue;
    			}
    			if (left == null || right == null) {
        
    					return false;
    			}
    			if (left.val != right.val) {
        
    				return false;
    			}
    			//将左节点的左孩子， 右节点的右孩子放入队列
    			queue.add(left.left);
    			queue.add(right.right);
    			//将左节点的右孩子，右节点的左孩子放入队列
    			queue.add(left.right);
    			queue.add(right.left);
    		}
    		return true;
    	}
    }

[dd34bbc519cd419c82b0759264cafddc.png]: https://img-blog.csdnimg.cn/dd34bbc519cd419c82b0759264cafddc.png
[3704be26e35b4a1db45338926f5011eb.png]: https://img-blog.csdnimg.cn/3704be26e35b4a1db45338926f5011eb.png