剑指 Offer 26. 树的子结构

题目描述

输入两棵二叉树A和B，判断B是不是A的子结构(约定空树不是任意一个树的子结构)。B是A的子结构， 即 A中有出现和B相同的结构和节点值。

题目链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/

思路

嵌套深度优先遍历，在递归遍历A的同时，当A，B节点值相等时，调用另一个递归函数递归遍历其左右节点

实现代码 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null){ //约定空树不是任意一个树的子结构
            return false;
        }
        //当前节点相等就遍历A，B的左右子树，左右子树都匹配成功才返回true
        if(A.val == B.val){
            if(isSub(A.left, B.left) && isSub(A.right, B.right)){
                return true;
            }
        }
        //不相等就就继续递归遍历A的左右节点
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    public boolean isSub(TreeNode root1, TreeNode root2){
        if(root2 == null){ //树B已匹配完，返回true
            return true;
        }
        if(root1 == null){ //树A先越过叶子节点，则匹配失败，返回false
            return false;
        }
        if(root1.val == root2.val){ //节点值相等就就继续递归遍历，返回左右节点的匹配结果
            return isSub(root1.left, root2.left) && isSub(root1.right, root2.right);
        }else{
            return false;
        }
    }
}

剑指 Offer 27. 二叉树的镜像

题目描述

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

思路

根据后序遍历左右中的特性，先遍历到叶子节点，再在回溯过程中交换左右节点

实现代码 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        TreeNode temp = left;
        root.left = right;
        root.right = temp;
        return root;
    }
}

剑指 Offer 28. 对称的二叉树

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

题目链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/

思路

前序遍历左右子树，左子树按中左右的顺序遍历，右子树按中右左的顺序遍历，比较镜像位置的节点值是否相同
即将左子树的左节点与镜像位置的右子树的右节点进行比较，相应的左的右节点与右的左节点进行比较。

实现代码 

/**
 * 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;
        }
        return leftAndRightTra(root.left, root.right);
    }
    public boolean leftAndRightTra(TreeNode left, TreeNode right){
        if(left == null || right == null){
            if(left == null && right == null){ //都为null，匹配，返回true
                return true;
            }else{ //一个为null，一个不为null，不匹配，返回false
                return false;
            }
        }
        if(left.val != right.val){ //若镜像位置的节点值不相等就返回false
            return false;
        }
        //递归遍历，左子树先左后右，右子树先右后左
        return leftAndRightTra(left.left, right.right) 
        && leftAndRightTra(left.right, right.left);
    }
}