自己买一台服务器做自己的网站,微信视频制作小程序,动漫视频制作软件,网页游戏网站556pk游戏福利平台java算法day13
104 二叉树的最大深度111 二叉树的最小深度226 翻转二叉树101 对称二叉树100 相同的树 104 二叉树的最大深度
我最开始想到的是用层序遍历。处理每一层然后计数。思路非常的清楚。 迭代法#xff1a;
/*** Definition for a binary tree node.* public class…java算法day13
104 二叉树的最大深度111 二叉树的最小深度226 翻转二叉树101 对称二叉树100 相同的树 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) {DequeTreeNode que new ArrayDeque();int deepth 0;//特判if(rootnull){return deepth;}//还是根节点先入栈。思想就是层序遍历。每处理完一层那么就计数1。que.offerLast(root);while(!que.isEmpty()){int size que.size();while(size0){TreeNode temp que.pollFirst();if(temp.left!null){que.offerLast(temp.left);}if(temp.right!null){que.offerLast(temp.right);}size--;}deepth;}return deepth;}
}递归解法在下面 111 二叉树的最小深度
我一开始想到的还是层序遍历。 唯一的变化就是判断什么时候停下来就是处理节点的时候如果某个节点没有叶子节点那不就说明这层之后该节点就没有孩子嘞。就是最小深度。 迭代解法
class Solution {public int minDepth(TreeNode root) {DequeTreeNode que new ArrayDeque();if(rootnull){return 0;}int count 1;que.offerLast(root);while(!que.isEmpty()){int size que.size();while(size0){TreeNode temp que.pollFirst();if(temp.leftnull temp.rightnull){return count;}if(temp.left!null){que.offerLast(temp.left);}if(temp.right!null){que.offerLast(temp.right);}size--;}count;}return count;}
}递归解法在下面 递归
接下来的题目几乎都用到了递归这里就解决晕递归的问题。 写递归的时候要注意哪些 1.不要一上来就扣细节而是考虑这个过程中要做什么。 2.停止递归逻辑处理逻辑正常返回逻辑
这种在题解中称为子问题和原问题模型。可以类比循环在循环中我们总是要执行相同的逻辑但是递归的特点在于他需要在这个过程中将计算的结果依次返给上一级。
想不到什么时候终止就想想最底部的状态。 想不到处理逻辑怎么写就想想如何进入下一层。
一句总结想想怎么递下去递到什么时候什么时候归归的过程中要干嘛。
二叉树的最大深度
思路 正如递归的核心思想不要上来就去扣递归的细节而是想递归的过程中做了什么。
递归的过程我做了什么最大的深度就是左子树和右子树当中的最大深度当返回上一层时进行1。
不从过程来考虑就是return的结果就是左右子树的最大深度然后到这一层嘞就是1。感觉就是一眼看到了问题的本质。底部自己会去递归。
class Solution {public int maxDepth(TreeNode root) {if(rootnull){return 0;}return Math.max(maxDepth(root.left),maxDepth(root.right))1;}}二叉树的最小深度
一上来先粗略的考虑这个思路是正确的粗略的考虑就是递归计算左右子树的最小深度每一层返回上来的时候再1。
这题如果按最大深度那样去想就做不出来了。因为一旦按那个套路去做就没想到这种情况。 如果按之前那个套路递归去算左右子树的最小高度那在第一个节点就会直接取到min这显然不是想要的答案。那显然这个时候就要把这种情况给排除。 排除的方式就是做判断 1.如果有一个节点为null了那么你要判断能不能往下走。两个节点都为null了你才可以停。 2.两个节点都不为null那就计算左右子树最小高度。 在递归的过程中计算左右最小深度。然后进行上面所说的特判。
class Solution {public int minDepth(TreeNode root) {if(rootnull){//递归出口能到这说明后面没路走了return 0;}//计算左右子树最小深度int leftDepth minDepth(root.left);int rightDepth minDepth(root.right);//对上面说的特殊情况做判断判断属于哪种if(root.leftnull){return rightDepth1;}if(root.rightnull){return leftDepth1;}//都不是上面说的两种情况那就是二者去min。return Math.min(leftDepth,rightDepth)1;}
}226 翻转二叉树
上来还是宏观上考虑就是节点的左右子树不停的做swap操作。如果节点空了就退出。
想到了就直接这么写。
/*** 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) {dfs(root);return root;}//每个节点都做reverse处理然后下一层还是对左右子树做同样的处理。public void dfs(TreeNode root){if(rootnull){return;}reverse(root);dfs(root.left);dfs(root.right);}//封装的一个函数。public void reverse(TreeNode root){TreeNode temp root.left;root.left root.right;root.right temp;}
}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) {//特判if(rootnull){return true;}//开始递归return dfs(root.left,root.right);}boolean dfs(TreeNode left,TreeNode right){//递归出口if(leftnull right null){return true;}//能走到这里上一个判断没有出去说明必有一为null。所以返回falseif(leftnull || right null){return false;}//走到这说明两个都不为null那就判断值if(left.val ! right.val){return false;}//往下一层走就是判断左节点的左孩子和右节点的右孩子。return dfs(left.left,right.right) dfs(left.right,right.left);}
}100 相同的树
这个更是简单。在递归的过程中单纯在比较二者左右孩子是否相等。
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(pnull q null){return true;}if(pnull || qnull){return false;}if(p.val ! q.val){return false;}return isSameTree(p.left,q.left) isSameTree(p.right,q.right);}
}
