LeetCode 100相同的树&101对称二叉树

梦里梦外; 2023-01-04 14:39 109阅读 0赞

> **微信搜一搜**：`bigsai`  
> **[大家都在关注的刷题、学习数据结构和算法宝藏项目][Link 1]**  
> 关注回复**进群**即可加入力扣打卡群，欢迎划水。近期打卡：  
> (https://bigsai.blog.csdn.net/article/details/111778579)  
> [LeetCode 96不同的二叉搜索树&95不同的二叉搜索树Ⅱ][LeetCode 96_95]  
> [LeetCode 97交错字符串(动态规划)][LeetCode 97]  
> [LeetCode 98验证二叉搜素树(中序遍历)&99恢复二叉搜索树][LeetCode 98_99]

## 相同的树 ##

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

输入:       1         1
              / \       / \
             2   3     2   3
    
            [1,2,3],   [1,2,3]
    
    输出: true

示例 2:

输入:      1          1
              /           \
             2             2
    
            [1,2],     [1,null,2]
    
    输出: false

示例 3:

输入:       1         1
              / \       / \
             2   1     1   2
    
            [1,2,1],   [1,1,2]
    
    输出: false

**分析：**  
结构相同，并且结构上的值也相同，这题很简单，使用一种遍历策略同时遍历比较节点是否都存在，如果存在值是否都相同即可，但是为了方便这里我使用递归的方法实现：

/**
     * 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 isSameTree(TreeNode p, TreeNode q) {
        
    		 if(p==null&&q==null)
    			 return true;
    		 if((p==null&&q!=null)||(p!=null&&q==null))
    			 return false;
    		 if(p.val!=q.val)
    			 return false;
    		 return isSameTree(p.left, q.left)&&isSameTree(p.right, q.right);
    	 }
    }

## 对称二叉树 ##

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 \[1,2,2,3,4,4,3\] 是对称的。

1
       / \
      2   2
     / \ / \
    3  4 4  3

但是下面这个 \[1,2,2,null,3,null,3\] 则不是镜像对称的:

1
       / \
      2   2
       \   \
       3    3

进阶：

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

**分析：**  
查看镜像对称，依然使用某种遍历方式，一个从左向右，一个从右向左顺序，查看遍历的每对节点是否相等。这里我就提供个人非递归解法：

/**
     * 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 isSymmetric(root.left,root.right);
    	 }
    
     private boolean isSymmetric(TreeNode left, TreeNode right) {
        
    	if((left==null)^(right==null))
    		return false;
    	if(left==null)
    		return true;
    	if(left.val!=right.val)
    		return false;
    	return isSymmetric(left.left, right.right)&&isSymmetric(left.right, right.left);
    	
     }
    }

原创不易，bigsai请你帮两件事帮忙一下:

1.  star支持一下， 您的肯定是我在平台创作的源源动力。
2.  微信搜索「**bigsai**」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见！

![image-20201114211553660][]

[Link 1]: https://github.com/javasmall/bigsai-algorithm
[LeetCode 96_95]: https://bigsai.blog.csdn.net/article/details/112093545
[LeetCode 97]: https://bigsai.blog.csdn.net/article/details/112134215
[LeetCode 98_99]: https://bigsai.blog.csdn.net/article/details/112135002
[image-20201114211553660]: /images/20221119/f7f421b3664248208f1934236ce2943f.png