101. 对称二叉树

递归三部曲：

1.确定递归函数的参数和返回值
返回值为boolen类型
2.确定终止条件
左节点为空，右节点不为空，不对称，return false;
左不为空，右为空，不对称 return false;
左右都为空，对称，return true;
左右都不为空，比较节点，不同就要return false;
3.确定单层递归的逻辑
比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
如果左右都对称就返回true ，有一侧不对称就返回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 isSymmetric(TreeNode root) {
        //一、确定递归函数的参数和返回值
        return compare(root.left,root.right);
    }

    //三、确定单层递归的逻辑
    private boolean compare(TreeNode left,TreeNode right){
        // 二、确定终止条件
        if(left==null && right!=null) return false;// 1.左节点为空，右节点不为空，不对称，return false;
        else if(left!=null && right==null) return false;//2.左不为空，右为空，不对称 return false;
        else if(left==null && right==null) return true; //3.左右都为空，对称，return true;
        else if(left.val!=right.val) return false; //比较值
        //4.左右都不为空，比较节点，不同就要return false;
        //比较内侧，左子树右侧，右子树左测
        boolean compareInside = compare(left.right,right.left);
        //比较外侧,左子树左侧，右子树右侧
        boolean compareOutside = compare(left.left,right.right);
        //比较根,左子树中、 右子树中（逻辑处理）
        boolean isSame = compareInside&&compareOutside;
        return isSame;
    }
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

方法二：迭代法

//使用迭代法判断，使用双端队列，相当于两个栈
     public boolean isSymmetric(TreeNode root) {
         Deque<TreeNode> deque =new  LinkedList<>();
         deque.offerFirst(root.left);
         deque.offerLast(root.right);
         while(!deque.isEmpty()){
             TreeNode leftNode = deque.pollFirst();
             TreeNode rightNode = deque.pollLast();
             //都为空，继续判断
             if(leftNode == null && rightNode == null){
                 continue;
             }
             //有一个为空或者值不等直接返回false，结束循环
             if(leftNode == null || rightNode==null || leftNode.val!=rightNode.val){
                 return false;
             }
             //放入左右子树的左右节点，注意对称放入
             deque.offerFirst(leftNode.left);
             deque.offerFirst(leftNode.right);
             deque.offerLast(rightNode.right);
             deque.offerLast(rightNode.left);
         }

         return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

方法三：迭代法,使用普通队列

    //迭代法,使用普通队列
    public boolean isSymmetric3(TreeNode root) {
        Queue<TreeNode> deque = new LinkedList<>();
        deque.offer(root.left);
        deque.offer(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.poll();
            TreeNode rightNode = deque.poll();
            if (leftNode == null && rightNode == null) {
                continue;
            }

            // 有一个为空或者值不等直接返回false，结束循环
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            // 这里顺序与使用Deque不同
            deque.offer(leftNode.left);
            deque.offer(rightNode.right);
            deque.offer(leftNode.right);
            deque.offer(rightNode.left);
        }
        return true;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25