当前位置:
- 首页
- /
- Java
- /
- 二叉树和递归的巩固--Java学习笔记(三)
二叉树和递归的巩固--Java学习笔记(三)
public class Solution {
public int max(int a,int b){
if(a>b){
return a;
}
else{
return b;
}
}
public int maxDepth(TreeNode root) {
int count=1;
if(root==null){
return 0;
}
if(root.left!=0||root.right!=0){
int leftMax=maxDepth(root.left);
int rightMax=maxDepth(root.right);
count=max(leftMax,rightMax)+1;
}
return count;
}
}
在以上程序的编写过程中,经历了各种千疮百孔,感觉又无数的红叉叉。后来发现是静态变量(static)始终没有搞懂。那么到底什么情况下需要加static?
1. 访问内部类的时候
2. 在一个类里面访问另一个类的时候
3. 访问一个类里面的特有数据时。
二、Same Tree(100)
Given two binary trees,write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
public class TheSameTree {
public static void main(String[] args) {
TreeNode root1=new TreeNode(1);
root1.left=new TreeNode(2);
root1.right=new TreeNode(3);
root1.left.left=new TreeNode(8);
TreeNode root2=new TreeNode(1);
root2.left=new TreeNode(2);
root2.right=new TreeNode(3);
root2.left.left=new TreeNode(8);
Solution A= new Solution();
System.out.print(A.isSameTree(root1, root2));
}
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public static class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q==null){
return true;
}
if(p==null||q==null){
return false;
}
if(p.val!=q.val){
return false;
}
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
}
}
这道题让我加深了对递归的理解(感觉其实还有很多没有掌握)
1.递归调用一定注意两个部分:if 和 return
2.一定是一层一层调用,再一层一层返回。
三、Balanced Binary Tree(110)
Given a binary tree,determine if it is height-balanced.
For this problem,a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
我的思路:1.先求出左子树的最大深度;2.再求出右子树的最大深度;3.再求出他们的绝对值小于1;
public static class Solution {
public boolean isBalanced(TreeNode root) {
int value=0;
if(root==null){
return true;
}
else{
int leftMaxNew=maxDepth(root.left);
int rightMaxNew=maxDepth(root.right);
value=leftMaxNew-rightMaxNew;
if((value<1)||(value>1)){
return false;
}
}
return isBalanced(root.left)&&isBalanced(root.right);
}
这就是本周我所做的三道题和一些简单感悟。这次做题最大的进步在于三道题都有自己的思路,不再是去背别人的答案,而是基本自己写出来的。虽然看上去可能很啰嗦,但是自己有进步就很开心。下周开始学习深度优先或者广度优先。加油!
来源: