BM31 题解 | #对称的二叉树#

解题思路：

其实就是双树递归，也叫同时递归，你看看单树递归和双树递归的样子，你就理解了，无非就是在单树递归的时候，传参里面，

多加了另一个树的参数而已。

单树递归

多树递归

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
     // 可以用层次遍历二叉树但是，一个右子树和左子树的情况，没有搞清楚。
     // bingo！终于搞清楚了，还是一样，空节点加入就可以了。

    public boolean isSymmetrical (TreeNode pRoot) {
        if(pRoot == null) {
            return true;
        }
        return preOrderTreeNode(pRoot.left, pRoot.right);
    }

    // 双树点递归
    boolean   preOrderTreeNode   ( TreeNode root1, TreeNode root2){
        if(root1 == root2) {
            return true;
        }
        // 1. vist T
        if(root1==null || root2==null || root1.val!=root2.val) {
            return false;
        }
        // 2. 递归 left
        boolean res1 = preOrderTreeNode(root1.left, root2.right);
        // 3. 递归 right
        boolean res2 = preOrderTreeNode(root1.right, root2.left);
        return res1 & res2;
    }

    int targetValue =  1111;

    boolean preOrderTreeNode(TreeNode root1) {
        if(root1 == null) {
            return true;
        }
        // 1. visit T
        if(root1.val != targetValue) {
            return false;
        }
        // 2. 递归left
        boolean res1 = preOrderTreeNode(root1.left);
        // 3. 递归right
        boolean res2 = preOrderTreeNode(root1.right);

        return res1 && res2;
    }


    public boolean isSymmetrical2 (TreeNode pRoot) {
        if(pRoot == null) {
            return true;
        }
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        q1.offer(pRoot.left);
        q2.offer(pRoot.right);
        while(!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode n1 = q1.poll();
            TreeNode n2 = q2.poll();

            if(n1 == null && n2 == null) {
                continue;
            }

            if(n1 == null || n2 == null || n1.val != n2.val) {
                return false;
            }

            // 能够走到这里nx都不会为空，
            // 因为前面的判断已经拦截了
            // 也就是空节点对空节点，不会入队
            q1.add(n1.left);
            q1.add(n1.right);

            q2.add(n2.right);
            q2.add(n2.left);
        }

        return true;
    }
}