leetcode题记:Symmetric Tree

爱被打了一巴掌 2022-05-18 07:50 220阅读 0赞

### 编程语言：JAVA ###

### 题目描述： ###

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
    
    For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
    
        1
       / \
      2   2
     / \ / \
    3  4 4  3
    But the following [1,2,2,null,3,null,3] is not:
        1
       / \
      2   2
       \   \
       3    3
    Note:
    Bonus points if you could solve it both recursively and iteratively.

### 提交反馈： ###

193 / 193 test cases passed.
    Status: Accepted
    Runtime: 16 ms
    Submitted: 1 minute ago
    You are here! 
    Your runtime beats 1.44 % of java submissions

### 解题思路： ###

题目判断树是否对称，借助上一道题【Same Tree】的思路，将根节点分成左右两个数，分别判断左右树是否对称。
    判断结束条件为：当前节点都为空，返回true；
    当前节点只有一个为空，返回false；
    当前值不相等，返回false；
    isSame(p.left,q.right) && isSame(p.right,q.left);
    
    这类型题目最主要的还是掌握递归思想吧，掌握了递归思想，简单题目大多都是递归思想。

### 代码： ###

/** * 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;
            }
            TreeNode p = root.left;
            TreeNode q = root.right;
    
            return isSame(p,q);
        }
        public boolean isSame(TreeNode p, TreeNode q){
    
            if(p == null && q == null){
                return true;
            }
            if(p == null || q == null){
                return false;
            }
            System.out.println(p.val + ":" + q.val);
            if(p.val != q.val){
                return false;
            }
    
            return isSame(p.left,q.right) && isSame(p.right,q.left);
        }
    }