（Java）二叉树的相关OJ题（相同的树，另一颗树的子树，对称二叉树或镜像二叉树，根据二叉树创建字符串）（内附OJ链接）

目录

1. 相同的树（LeetCode100）相同的树

2. 另一颗树的子树（LeetCode572）另一颗树的子树

3.  对称二叉树或者镜像二叉树（LeetCode101）对称二叉树 

4. 根据二叉树创建字符串（LeetCode606）根据二叉树创建字符串 

1. 相同的树（LeetCode100）相同的树

题目：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。例：

可以点开上述链接查看题目，具体做法如下：

1. 判空，当两个树都为空时，也认为是相同的二叉树，则返回false

2. 当有一颗树为空一颗树不为空，则这两颗树必定不相同，返回false

3. 当两棵树的根节点都不为空时，判断两棵树结点的元素是否相同

4. 递归判断两棵树根的左子树与根的右子树

参考代码：

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p == null && q == null){return true;}if(p == null || q == null){return false;}return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);  }
}

2. 另一颗树的子树（LeetCode572）另一颗树的子树

题目：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

简单概括就是判断一颗树中是否包含另一颗树。例如：

可以点开上述链接查看题目，具体做法如下：

1. 判空，当root与subRoot都为空时，我们认为满足题目要求，则返回true

2. 当root与subRoot只有个为空时，返回false

3. 当root与subRoot都不为空时，判断两个树是否为同一棵树

4. 递归判断root的左子树与subRoot

5. 递归判断root的右子树与subRoot

注意：这里的判断两颗树是否为同一颗树刚好是上一个题，所以直接用上一个题的方法即可，做法中的3，4 ，5满足一条即满足题目要求，所以将他们用  | |  连接起来返回即可。

参考代码：

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p==null&&q==null){return true;}if(p==null||q==null){return false;}return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);  }public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root==null&&subRoot==null){return true;}if(root==null||subRoot==null){return false;}return isSameTree(root,subRoot)||isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);}
}

3.  对称二叉树或者镜像二叉树（LeetCode101）对称二叉树 

题目：给定一个二叉树，检查它是否是镜像对称的。例：

可以点开上述链接查看题目，具体做法如下：

1. 判空，当二叉树的根为空时，认为满足题目要求返回true

2. 当根不为空时，我们需要判断根的左子树与右子树的情况

3. 这里判断根的左子树与右子树的情况，我们可以写一个方法来递归判断

将上述进行画图说明：

参考代码：

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

4. 根据二叉树创建字符串（LeetCode606）根据二叉树创建字符串 

题目：你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。例：

可以点开上述链接查看题目，具体做法如下：

注意：因为有字符串的追加，我们选择StringBuilder创建对象，这样比字符串的拼接效率高

1. 题目要求前序遍历，前序遍历顺序：左---根---右

2. 先进行判空，当根为空时直接返回，当根不为空先追加根的值

3. 当根的左子树为空时，判断根的右子树是否为空，当根的右子树也为空时直接返回，当根的右子树不为空时，追加 "()" 

4. 当根的左子树不为空时，先追加 "(" ，在递归遍历root.left，最后追加 ")" 

5. 根的左子树已经处理完了

6. 在处理根的右子树，当根的右子树为空时，直接返回

7. 当根的右子树不为空时先追加 "(" ，在递归遍历root.right，最后追加 ")" 

参考代码：

class Solution {public String tree2str(TreeNode root) {StringBuilder s = new StringBuilder();tree2str(root,s);return s.toString();}public void tree2str(TreeNode root,StringBuilder s){if(root == null){return;}s.append(root.val);if(root.left == null){if(root.right == null){return;}else{s.append("()");}}else{s.append('(');tree2str(root.left,s);s.append(')');}if(root.right == null){return;}else{s.append('(');tree2str(root.right,s);s.append(')');}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！