【剑指offer第7天】搜索与回溯算法（简单）

心已赠人 2022-09-11 07:12 181阅读 0赞

#### 第一题 ####

判断树的子结构  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16]  
先序遍历并使用递归判断树的子结构，注意在helper函数中判断的顺序，if(root2=null)这个条件要放在前面，否则出现A和B都判断到最后一个结点的时候错误的返回if(root1=null)即false

class Solution { 
        public boolean isSubStructure(TreeNode A, TreeNode B) { 
            if(A == null||B == null){ return false;}
            if(helper(A,B)){ return true;}
            if(isSubStructure(A.left,B)||isSubStructure(A.right,B)){ return true;}
            return false;
        }
        public boolean helper(TreeNode root1,TreeNode root2){ 
            if(root2 == null){ return true;}
            if(root1 == null){ return false;}
            if(root1.val == root2.val){ 
                return helper(root1.left,root2.left)&&helper(root1.right,root2.right);
            }
            return false;
        }
    }

#### 第二题 ####

二叉树的镜像  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
使用递归求解

class Solution { 
        public TreeNode mirrorTree(TreeNode root) { 
            if(root == null){ return null;}
            TreeNode tmp = new TreeNode(root.val);
            helper(root,tmp);
            return tmp;
        }
        public void helper(TreeNode root,TreeNode tmp){ 
            if(root.left == null && root.right == null){ return;}
            if(root.left != null){ 
                tmp.right = new TreeNode(root.left.val);
                helper(root.left,tmp.right);
            }
            if(root.right != null){ 
                tmp.left = new TreeNode(root.right.val);
                helper(root.right,tmp.left);
            }
        }
    }

简洁版递归

//使用递归
    class Solution { 
        public TreeNode mirrorTree(TreeNode root) { 
            if(root == null){ return null;}
            TreeNode right = mirrorTree(root.right);
            TreeNode left = mirrorTree(root.left);
            root.left = right;
            root.right = left;
            return root;
        }
    }

#### 第三题 ####

对称二叉树 使用递归求解  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16 2]

class Solution { 
        public boolean isSymmetric(TreeNode root) { 
            if(root == null){ return true;}
            return recur(root.left,root.right);
        }
        public boolean recur(TreeNode left,TreeNode right){ 
            if(left == null&&right == null){ return true;}
            if(left == null||right == null){ return false;}
            if(left.val == right.val&&recur(left.left,right.right)&&recur(right.left,left.right)){ return true;}
            return false;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c85944ec6f1b441fb0de59016dc0c424.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/f42a1f418a304c7287d89dda72eef23c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/c3bcbc13870645d99f3f3b371a266621.png