算法打卡第十二弹——二叉树
文章目录
- part01 翻转二叉树
- 方法一：递归前序遍历
- 方法二：递归后序遍历
- part02 对称二叉树
- 相同的树
- 另一个树的子树
- part03 二叉树的最大深度
- part04 二叉树的最小深度
跟着代码随想录刷题的第十二天。
代码随想录链接：代码随想录
part01 翻转二叉树
题目链接：226.翻转二叉树
代码：
方法一：递归前序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null)
return null;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
方法二：递归后序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null)
return null;
invertTree(root.left);
invertTree(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
return root;
}
}
题解：该题使用的是递归的前序遍历
part02 对称二叉树
题目链接：101. 对称二叉树
代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
TreeNode right = root.right;
TreeNode left = root.left;
boolean result = isTrue(left,right);
return result;
}
public boolean isTrue(TreeNode left,TreeNode right){
if(right==null&&left!=null)
return false;
else if(right!=null&&left==null)
return false;
else if(right==null&&left==null)
return true;
else if(right.val!=left.val)
return false;
boolean outside = isTrue(left.left,right.right);
boolean inside = isTrue(left.right,right.left);
boolean result = outside&&inside;
return result;
}
}
题解：这道题的关键点在于应该怎样比较子节点。选择的是后序遍历，这样可以将子节点比较之后的结果传回到父节点。我最开始做这道题的时候，不知道应该将比较结果延续下去，就一直卡着。
相同的树
题目链接：100. 相同的树
代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q!=null)
return false;
else if(p!=null&&q==null)
return false;
else if(p==null&&q==null)
return true;
else if(p.val!=q.val)
return false;
boolean left = isSameTree(p.left,q.left);
boolean right = isSameTree(p.right,q.right);
return left&&right;
}
}
另一个树的子树
题目链接：572.另一个树的子树
代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root==null&&subRoot!=null)
return false;
else if(root!=null&&subRoot==null)
return true;
boolean a1 = isSubtree(root.left,subRoot);
boolean a2 = isSubtree(root.right,subRoot);
boolean a3 = isSame(root,subRoot);
return a1||a2||a3;
}
public boolean isSame(TreeNode p,TreeNode q){
if(p==null&&q!=null)
return false;
else if(p!=null&&q==null)
return false;
else if(p==null&&q==null)
return true;
else if(p.val!=q.val)
return false;
boolean left = isSame(p.left,q.left);
boolean right = isSame(p.right,q.right);
return left&&right;
}
}
题解：本题用了两次递归，在比较相同的时候就和之前一样，但是得用递归来比较root函数的子树和目标二叉树。
part03 二叉树的最大深度
题目链接：104.二叉树的最大深度
代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null)
return 0;
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
题解：是后序遍历
part04 二叉树的最小深度
题目链接：111.二叉树的最小深度
代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
return getDepth(root);
}
public int getDepth(TreeNode root){
if(root==null)
return 0;
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
if(root.left==null&&root.right!=null)
return 1+rightDepth;
else if(root.left!=null&&root.right==null)
return 1+leftDepth;
return 1+Math.min(leftDepth,rightDepth);
}
}
题解：这道题会遇到误区，我最开始将求最大深度的代码修改了一下，但是错误的。后面发现只写1+Math.min(leftDepth,rightDepth)会导致遇到一个节点，其左节点是空，右节点不是，或者反之，都会直接返回了，然而这并不是叶子结点，也就不是最小深度。