【题28 对称的二叉树】

淩亂°似流年 2022-03-25 13:20 78阅读 0赞

**【题28 对称的二叉树】**  
**【题目】**  
请实现一个函数，用来判断一棵二叉树是不是对称的，如果一棵二叉树和他的镜像一样，那么它是对称的  
**例如：**  
如图的3棵二叉树，第一棵二叉树是对称的，另外两棵不是  
![在这里插入图片描述][20190121102643785.png]  
**三种二叉树遍历算法：**  
前序遍历，中序遍历和后序遍历都是先遍历左子节点再遍历右子节点。  
**定义一种遍历算法：**  
先遍历右子节点再遍历左子节点。即先遍历父节点，再遍历它的右子节点，最后遍历它的左子节点。  
![在这里插入图片描述][20190121102655849.png]  
**树1，**  
前序遍历\{8，6，5，7，6，7，5\}  
定义遍历\{8，6，5，7，6，7，5\} 序列一样  
![在这里插入图片描述][2019012110270559.png]  
**树2，**  
前序遍历\{8，6，5，7，9，7，5\}  
定义遍历\{8，9，5，7，6，7，5\} 不一样  
![在这里插入图片描述][20190121102717690.png]  
**树3：**  
前序遍历\{7，7，7，7，7，7\}  
定义遍历\{7，7，7，7，7，7\} 虽然一样，但并不对称  
**解决方法：定义一个空指针null**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20190121102741772.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20190121102753240.png]

通过比较二叉树的前序遍历序列和对称遍历序列来判断二叉树是不是对称的，  
如果两个序列一致，那么是对称的。  
**实现**

/*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    import java.util.Stack;
    public class Solution {
        boolean isSymmetrical(TreeNode pRoot)
        {
            if(pRoot == null) return true;
            Stack<TreeNode> s = new Stack<>();
            s.push(pRoot.left);
            s.push(pRoot.right);
            while(!s.empty()){
                TreeNode right = s.pop();//成对取出
                TreeNode left = s.pop();
                if(right == null && left == null) continue;
                if(right == null || left == null) return false;
                if(right.val != left.val) return false;
                //成对插入
                s.push(left.left);
                s.push(right.right);
                s.push(left.right);
                s.push(right.left);
            }
            return true;
        }
    }

参考  
1。《剑指offer》

[20190121102643785.png]: /images/20220325/741c486675d740df92a31a027122777f.png
[20190121102655849.png]: /images/20220325/aa05166a951b452c9ac42a5806b79a7a.png
[2019012110270559.png]: /images/20220325/3b6f2461a5e04e94b6d0133507c09b46.png
[20190121102717690.png]: /images/20220325/93d4dfafd9fe44f6864942cf3f05d0d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220325/63f3aa6d6a514b1e92b41b066cf5b485.png
[20190121102741772.png]: /images/20220325/0e35aee8564a4b2093b30ee7f0968e66.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20220325/efed561b93304cd3a6d114d1c4bbafcc.png
[20190121102753240.png]: /images/20220325/1c3247d27b1740f1bdd7b7cac7fdf5ee.png