java算法day13

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) {Deque<TreeNode> que = new ArrayDeque<>();int deepth = 0;//特判if(root==null){return deepth;}//还是根节点先入栈。思想就是层序遍历。每处理完一层，那么就计数+1。que.offerLast(root);while(!que.isEmpty()){int size = que.size();while(size>0){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) {Deque<TreeNode> que = new ArrayDeque<>();if(root==null){return 0;}int count = 1;que.offerLast(root);while(!que.isEmpty()){int size = que.size();while(size>0){TreeNode temp = que.pollFirst();if(temp.left==null && temp.right==null){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(root==null){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(root==null){//递归出口，能到这说明后面没路走了return 0;}//计算左右子树最小深度int leftDepth = minDepth(root.left);int rightDepth = minDepth(root.right);//对上面说的特殊情况做判断，判断属于哪种if(root.left==null){return rightDepth+1;}if(root.right==null){return leftDepth+1;}//都不是上面说的两种情况，那就是二者去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(root==null){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(root==null){return true;}//开始递归return dfs(root.left,root.right);}boolean dfs(TreeNode left,TreeNode right){//递归出口if(left==null && right == null){return true;}//能走到这里，上一个判断没有出去，说明必有一为null。所以返回falseif(left==null || 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(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);}
}