文章目录
JZ26 树的子结构
题目描述
思路详解
本题我们使用两层前序遍历
既然是要找到A树中是否有B树这样子树，如果是有子树肯定是要遍历这个子树和B树，将两个的节点一一比较，但是这样的子树不一定就是A树根节点开始的，所以我们还要先找到子树可能出现的位置。
既然是可能的位置，那我们可以对A树的每个节点前序递归遍历，寻找是否有这样的子树，而寻找是否有子树的时候，我们就将A树与B树同步前序遍历，依次比较节点值。
代码与结果
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 { private boolean recursion(TreeNode root1, TreeNode root2){ //当一个节点存在另一个不存在时 if(root1 == null && root2 != null) return false; //两个都为空则返回 if(root1 == null || root2 == null) return true; //比较节点值 if(root1.val != root2.val) return false; //递归比较子树 return recursion(root1.left, root2.left) && recursion(root1.right, root2.right); } public boolean HasSubtree(TreeNode root1, TreeNode root2) { //空树 if(root2 == null) return false; //一个为空，另一个不为空 if(root1 == null && root2 != null) return false; if(root1 == null || root2 == null) return true; //递归比较 boolean flag1 = recursion(root1, root2); //递归树1的每个节点 boolean flag2 = HasSubtree(root1.left, root2); boolean flag3 = HasSubtree(root1.right, root2); return flag1 || flag2 || flag3; } }
JZ27 二叉树的镜像
题目描述
思路详解
因为我们需要将二叉树镜像，意味着每个左右子树都会交换位置，如果我们从上到下对遍历到的节点交换位置，但是它们后面的节点无法跟着他们一起被交换，因此我们可以考虑自底向上对每两个相对位置的节点交换位置，这样往上各个子树也会被交换位置。
自底向上的遍历方式，我们可以采用后序递归的方法。
代码与结果
JZ28 对称的二叉树
题目描述
思路详解
前序遍历的时候我们采用的是“根左右”的遍历次序，如果这棵二叉树是对称的，即相应的左右节点交换位置完全没有问题，那我们是不是可以尝试“根右左”遍历，按照轴对称图像的性质，这两种次序的遍历结果应该是一样的。
不同的方式遍历两次，将结果拿出来比较看起来是一种可行的方法，但也仅仅可行，太过于麻烦。我们不如在遍历的过程就结果比较了。而遍历方式依据前序递归可以使用递归：
终止条件： 当进入子问题的两个节点都为空，说明都到了叶子节点，且是同步的，因此结束本次子问题，返回true；当进入子问题的两个节点只有一个为空，或是元素值不相等，说明这里的对称不匹配，同样结束本次子问题，返回false。
返回值： 每一级将子问题是否匹配的结果往上传递。
本级任务： 每个子问题，需要按照上述思路，“根左右”走左边的时候“根右左”走右边，“根左右”走右边的时候“根右左”走左边，一起进入子问题，需要两边都是匹配才能对称。
代码与结果
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 { boolean recursion(TreeNode root1, TreeNode root2){ //可以两个都为空 if(root1 == null && root2 == null) return true; //只有一个为空或者节点值不同，必定不对称 if(root1 == null || root2 == null || root1.val != root2.val) return false; //每层对应的节点进入递归比较 return recursion(root1.left, root2.right) && recursion(root1.right, root2.left); } boolean isSymmetrical(TreeNode pRoot) { return recursion(pRoot, pRoot); } }
