LeetCode 101. 对称二叉树 ＆＆ 100. 相同的树 ＆＆ 572. 另一棵树的子树

101.对称二叉树

题目解析：递归

下面介绍递归三部曲：

1. 确定递归函数的参数和返回值

   因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。返回值自然是boolean类型。
   
   代码如下：
   
   bool compare(TreeNode left, TreeNode right)
   

2. 确定终止条件

   要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。
   
   节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）
   1. 左右都为空，对称，返回true
   2. 左节点为空，右节点不为空，不对称，return false
   3. 左不为空，右为空，不对称 return false
   4. 左右都不为空，比较节点数值，不相同就return false
   
   此时左右节点不为空，且数值也不相同的情况我们也处理了。
   
   代码如下：
   if (left == NULL && right != NULL) return true;
   if (left== NULL || right == NULL) return false;
   if (left->val != right->val) return false;
   
   我们把以上情况都排除之后，剩下的就是 左右节点都不为空，且数值相同的情况。
   

3. 确定单层递归的逻辑

   此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。
   
       比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
       比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
       如果左右都对称就返回true ，有一侧不对称就返回false 。
   
   代码如下：
   
   bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
   bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
   bool isSame = outside && inside;                    // 左子树：中、 右子树：中（逻辑处理）
   return isSame;
   

代码实现：

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 true;
        } 
        if(left == null || right == null){
    
            return false;
        } 
        if(left.val != right.val){
    
            return false;
        }
			 // 树的外侧进行比较
        boolean outside = compare(left.left, right.right);
        // 树的内侧进行比较哦啊
        boolean inside = compare(left.right, right.left);

        return outside && inside;
    }
}

100.相同的树

代码实现：

class Solution {
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
    
        return compare(p, q);
    }

    private boolean compare(TreeNode p, TreeNode q){
    
        if(left == null && right == null){
    
            return true;
        } 
        if(left == null || right == null){
    
            return false;
        } 
        if(left.val != right.val){
    
            return false;
        }

        // 两棵树的左边进行比较
        boolean outCompare = compare(p.left, q.left);  // 一个树比较外侧和内侧， 两棵树比较的为同一侧
        // 两棵树的右边进行比较
        boolean inCompare = compare(p.right, q.right);

        return outCompare && inCompare;
    }
}

572.另一棵树的子树

代码实现(层序遍历 + 递归)：

class Solution {
    
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    
        // 声明一个辅助队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
    
            int len = queue.size();
            while(len > 0){
    
                TreeNode tempNode = queue.poll();
                if(compare(tempNode, subRoot)){
      // 比较compare(tempNode, subRoot) 非compare(root, subRoot)
                    return true;
                }
                if(tempNode.left != null) queue.offer(tempNode.left);
                if(tempNode.right != null) queue.offer(tempNode.right);
                len--;
            }
        }

        return false;

    }

    public boolean compare(TreeNode p, TreeNode q){
    
        if(p == null && q == null){
    
            return true;
        }

        if(p == null || q == null){
    
            return false;
        }

        if(p.val != q.val){
    
            return false;
        }

        return compare(p.left, q.left) && compare(p.right, q.right);
    }
}