【剑指offer第7天】搜索与回溯算法(简单) 心已赠人 2022-09-11 07:12 129阅读 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
还没有评论,来说两句吧...