|
录哥打卡
1.树的迭代遍历
前序遍历
思路
用栈作为存储结构。每次都是先把根节点放进去，然后把根节点取出，然后就是把根节点的右子节点放进去，再放左子节点。那么下次取出来的就是左子树的根节点，再把左子树的右子节点放进去，再放左子树的左子节点。如此类推。就发现它的处理顺序是中左右。只有先放根节点进去，取出根节点，再放右子节点，和左子节点，就能够保证处理的顺序是前序遍历的顺序。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if(root==null){
return new ArrayList<Integer>();
}
List<Integer> res=new ArrayList<>();
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.pop();
res.add(node.val);
if(node.right!=null){
stack.push(node.right);
}
if(node.left!=null){
stack.push(node.left);
}
}
return res;
}
}
中序遍历
思路
不能够直接用前序遍历的模板原因是前序遍历取出的点刚好就是中间点也是要访问的点。但是中序遍历要访问的点并不是中间点，中间点是只有访问到最左的节点的时候，没有左子树了，那么栈弹出来最左边的节点才是要处理的中间节点，接着就要往右子树的左边开始遍历。本质就是左中右
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
if(root==null){
return res;
}
TreeNode cur=root;
Stack<TreeNode> stack=new Stack<>();
while(cur!=null||!stack.isEmpty()){
if(cur!=null){
stack.push(cur);
cur=cur.left;
}else{
cur=stack.peek();
stack.pop();
res.add(cur.val);
cur=cur.right;
}
}
return res;
}
}
后序遍历
思路
前序遍历是中左右，那么后序遍历实际上就是左右中，只需要调换前序遍历中右左的遍历方式，然后调转整个list的结果就是后序遍历的结果。
拓展
root可能为null需要提前判断。
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
if(root==null){
return res;
}
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.pop();
res.add(node.val);
if(node.left!=null){
stack.push(node.left);
}
if(node.right!=null){
stack.push(node.right);
}
}
Collections.reverse(res);
return res;
}
}
统一遍历方式
思路
①标记法，也就是按照遍历顺序的倒过来的顺序进栈，并且给需要处理的中间节点打上标记。那么下次只要遍历到标记那么就证明这个是处理的节点。
②看清模板的本质，实质上就是修改加入处理节点的位置而已(标记)
前序遍历模板
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
if(root==null) return res;
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.peek();
if(node!=null){
stack.pop();
if(node.right!=null) stack.push(node.right);
stack.push(node);
stack.push(null);
if(node.left!=null) stack.push(node.left);
}else{
stack.pop();
TreeNode temp=stack.peek();
stack.pop();
res.add(temp.val);
}
}
return res;
}
}
层序遍历
思路
使用队列的先进先出，先进其中一层的所有节点，然后遍历，并且获取所有节点的孩子节点，并且再次遍历。如此类推。问题是你怎么知道什么时候是一层？需要用一个size来限定，先进queue的是根节点，那么自然就是大小为1，接着就是弹出根节点，然后遍历第一层并获取第二层的节点，也就是根节点的孩子节点。最后就会发现队列里面刚好只有第二层节点，下面也是这样，计算每层大小之后，然后再获取孩子节点。
总结：层序遍历就是从头到尾，符合队列的先进先出，也就是谁先进来谁先处理。每层的大小可以通过队列size来限定后，再加入新的子节点。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue=new LinkedList<>();
List<List<Integer>> res=new ArrayList<>();
if(root==null) return res;
queue.offer(root);
while(!queue.isEmpty()){
int len=queue.size();
List<Integer> list=new ArrayList<>();
while(len>0){
TreeNode node=queue.poll();
list.add(node.val);
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
len--;
}
res.add(list);
}
return res;
}
}
2.反转二叉树
思路
①前序遍历交换左子树和右子树
②后序遍历
③中序遍历会导致交换了两次树，无法做到反转
④层序遍历，也是直接交换左子树和右子树
class Solution {
public TreeNode invertTree(TreeNode root) {
Queue<TreeNode> queue=new LinkedList<>();
if(root==null) return root;
queue.add(root);
while(!queue.isEmpty()){
int size=queue.size();
while(size-->0){
TreeNode node=queue.poll();
TreeNode temp=node.left;
node.left=node.right;
node.right=temp;
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
}
return root;
}
}
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) return root;
TreeNode node=root.left;
root.left=root.right;
root.right=node;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
3.对称二叉树
递归
思路
①判断参数，需要遍历两棵树，左子树和右子树
②第二个就是终止条件
（1）左子树空，右不空（反过来也是）
（2）左右都是空
（3）左右的值不对应
③处理逻辑，就是判断左子树与右子树的后序遍历是否成功对称，如果是就是true不是就是false
class Solution {
public boolean isSymmetric(TreeNode root) {
return compare(root.left,root.right);
}
public boolean compare(TreeNode left,TreeNode right){
if(left==null&&right!=null) return false;
if(left!=null&&right==null) return false;
if(left==null&&right==null) return true;
if(left.val!=right.val) return false;
boolean outside= compare(left.left,right.right);
boolean inside=compare(left.right,right.left);
return outside&&inside;
}
}
迭代法
思路
相当于就是广度优先遍历两个树来进行的对比。把左子树和右子树同时放到queue，然后每次取出两个进行对比，接着就是把左子树和右子树对比的节点，左子树的左子节点对上右子树的右子节点，左子树的右子节点对上右子树的左子节点两两放入队列，等待下一次的对比。知道队列为空。而且判断需要在放入子节点队列之前做条件判断
①两个空->continue
②其中一边是空的->false
③值不相同->false
class Solution {
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while(!queue.isEmpty()){
TreeNode leftNode=queue.poll();
TreeNode rightNode=queue.poll();
if(leftNode==null&&rightNode==null){
continue;
}
if(leftNode==null||rightNode==null||leftNode.val!=rightNode.val){
return false;
}
queue.offer(leftNode.left);
queue.offer(rightNode.right);
queue.offer(leftNode.right);
queue.offer(rightNode.left);
}
return true;
}
}
栈（双端队列）
思路
把双端队列当成两个栈，只需要保证对应关系相同即可，也就是出栈的那两个节点一定是对比的节点，其它基本跟队列的思想一致。
class Solution {
public boolean isSymmetric(TreeNode root) {
Deque<TreeNode> deque=new LinkedList<>();
deque.offerFirst(root.left);
deque.offerLast(root.right);
while(!deque.isEmpty()){
TreeNode leftNode= deque.pollFirst();
TreeNode rightNode= deque.pollLast();
if(leftNode==null&&rightNode==null){continue;}
if(leftNode==null||rightNode==null||leftNode.val!=rightNode.val){
return false;
}
deque.offerFirst(leftNode.left);
deque.offerFirst(leftNode.right);
deque.offerLast(rightNode.right);
deque.offerLast(rightNode.left);
}
return true;
}
}
4.树的最大深度
递归法
思路
①后序遍历，递归三部曲，参数遍历的子树，返回值就是深度，结束条件就是遍历到空节点的时候。解决逻辑就是左子树和右子树最大深度+本层深度1。
②前序遍历，其实就是每次进来的时候都需要更新结果，并且在进入左右子树的时候给深度+1。判断结束条件是左子树和右子树都是空，如果其中一个不空那么就可以进入新的递归深度+1，并且回溯深度-1。交给下一个子树进行回溯的操作。重点是注意终结条件是两个子树都是空，进入递归的判断是左子树不空或者是右子树不空，这个是前序遍历的不同。但是本质相似。相当于每次都在本层先做一个处理
class Solution {
public int maxDepth(TreeNode root) {
if(root==null) return 0;
int left=maxDepth(root.left);
int right=maxDepth(root.right);
int depth=Math.max(left,right)+1;
return depth;
}
}
class Solution {
int result=0;
public void getDepth(TreeNode node,int depth){
result=depth>result?depth:result;
if(node.left==null&&node.right==null) return;
if(node.left!=null){
depth++;
getDepth(node.left,depth);
depth--;
}
if(node.right!=null){
depth++;
getDepth(node.right,depth);
depth--;
}
return ;
}
public int maxDepth(TreeNode root) {
if(root==null) return 0;
getDepth(root,1);
return result;
}
}
迭代法
思路
①层序遍历模板+depth计算。
class Solution {
public int maxDepth(TreeNode root) {
Queue<TreeNode> queue=new LinkedList<>();
if(root==null) return 0;
queue.offer(root);
int depth=0;
while(!queue.isEmpty()){
int size=queue.size();
depth++;
while(size-->0){
TreeNode node=queue.poll();
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
}
return depth;
}
}
n叉树的最大深度
递归法
思路
①后序遍历。只不过就是for循环而已跟上面没什么区别
②层序遍历，同上
总结：递归遍历如果树是平衡那么空间复杂度logn低于层序遍历的空间复杂度n。但是时间复杂度是一样
class Solution {
public int maxDepth(Node root) {
if(root==null) return 0;
int depth=0;
for(Node node:root.children){
depth=Math.max(depth,maxDepth(node));
}
depth=depth+1;
return depth;
}
}
class Solution {
public int maxDepth(Node root) {
Queue<Node> queue=new LinkedList<>();
if(root==null) return 0;
queue.offer(root);
int depth=0;
while(!queue.isEmpty()){
int size=queue.size();
depth++;
while(size-->0){
Node node=queue.poll();
for(Node temp:node.children){
if(temp!=null){
queue.offer(temp);
}
}
}
}
return depth;
}
}
5.树的最小深度
递归法
思路
①后序遍历，但是需要注意题目要求是根节点到叶子节点的最小深度。如果根节点没有左子树或者是右子树，出现的问题就是，最后得出的深度就是1，也就是根节点到根节点的深度。而这个地方需要特殊处理，如果发现最小深度的节点不是叶子节点，那么就要把深度改成当前节点深度1+隔壁子树的深度。其实也就说明这个节点就是根节点。
class Solution {
public int minDepth(TreeNode root) {
if(root==null) return 0;
int left=minDepth(root.left);
int right=minDepth(root.right);
if(root.left!=null&&root.right==null){
return 1+left;
}
if(root.right!=null&&root.left==null){
return 1+right;
}
int depth=Math.min(left,right)+1;
return depth;
}
}
迭代法
思路
①层次遍历模板+depth自增+判断是不是叶子节点，然后更新最小的结果。
②但是更新就没有用到层序遍历的特点，层序遍历只要一发现最小，那么就可以立刻返回，因为这个肯定是最小，因为他是一层一层往下面遍历。广度优先遍历的查询最小深度优势更大。
总结：层序遍历本质不变，实际上还是在遍历，但是不同的就是处理逻辑不同，解决最终问题不同。但是问题的本质就是让你遍历树，然后根据细节进行逻辑处理。
class Solution {
public int minDepth(TreeNode root) {
int depth=0;
Queue<TreeNode> queue=new LinkedList<>();
if(root==null) return 0;
queue.offer(root);
int res=Integer.MAX_VALUE;
while(!queue.isEmpty()){
int size=queue.size();
boolean flag=true;
depth++;
while(size-->0){
TreeNode node=queue.poll();
if(node.left==null&&node.right==null){
res=Math.min(res,depth);
}
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
}
return res;
}
}
class Solution {
public int minDepth(TreeNode root) {
int depth=0;
Queue<TreeNode> queue=new LinkedList<>();
if(root==null) return 0;
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
boolean flag=true;
depth++;
while(size-->0){
TreeNode node=queue.poll();
if(node.left==null&&node.right==null){
return depth;
}
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
}
return depth;
}
}
6.完全二叉树的节点个数
思路
①后序遍历+ （统计左右子树个数+1）
②层序遍历直接统计个数
class Solution {
public int countNodes(TreeNode root) {
if(root==null) return 0;
int left=countNodes(root.left);
int right=countNodes(root.right);
int count=left+right+1;
return count;
}
}
class Solution {
public int countNodes(TreeNode root) {
Queue<TreeNode> queue=new LinkedList<>();
if(root==null) return 0;
queue.offer(root);
int res=0;
while(!queue.isEmpty()){
int size=queue.size();
while(size-->0){
TreeNode node=queue.poll();
res++;
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
}
return res;
}
}
7.平衡二叉树
递归法
思路
①与求最大深度相似。但是不同的就是要加上一个处理就是left与right的高度差如果大于1那么就直接返回-1的深度。平衡二叉树就是每个节点的子树高度差小于等于1。抓住这一点，然后就是递归三部曲，返回的是深度，也可以说是高度。因为求的是子树最大深度，然后再回到根节点的时候对比左右子树的大小，然后往上递归。如果返回-1就一直往上返回，如果是有对应高度返回就要计算他们的高度差。
②高度：从下到上通常是后序遍历
深度：从上到下通常是前序遍历
class Solution {
public boolean isBalanced(TreeNode root) {
int res=getDepth(root);
return res!=-1;
}
public int getDepth(TreeNode root){
if(root==null) return 0;
int left=getDepth(root.left);
if(left==-1) return -1;
int right=getDepth(root.right);
if(right==-1) return -1;
if(Math.abs(left-right)>1){
return -1;
}else{
int depth=1+Math.max(left,right);
return depth;
}
}
}
迭代法
思路
①这个不好理解，而且效率很差，每次重复计算最大深度。
②这里面的depth记录的当前访问层的深度，只要这层弹出那么就要depth–。如果是访问新的一层那么就要depth++;
class Solution {
public int getDepth(TreeNode root){
if(root==null) return 0;
int depth=0;
int res=0;
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.peek();
if(node!=null){
stack.pop();
stack.push(node);
stack.push(null);
depth++;
if(node.right!=null) stack.push(node.right);
if(node.left!=null) stack.push(node.left);
}else{
stack.pop();
TreeNode temp=stack.peek();
stack.pop();
depth--;
}
res=res>depth?res:depth;
}
return res;
}
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.peek();
stack.pop();
if(Math.abs(getDepth(node.left)-getDepth(node.right))>1){
return false;
}
if(node.right!=null) stack.push(node.right);
if(node.left!=null) stack.push(node.left);
}
return true;
}
}
8.二叉树所有路径
递归法
思路
①使用回溯，每次在走到下一个点先判空，并加入下一个点的值，回溯回来的时候去掉这个值。最后得出所有的方案。
这种是属于回溯的做法。先加入下一个节点的val和进入再加都是一样的
class Solution {
List<String> res=new ArrayList<>();
List<Integer> list=new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
if(root==null) return res;
list.add(root.val);
findPath(root);
return res;
}
public void findPath(TreeNode root){
if(root.left==null&&root.right==null){
StringBuilder sb=new StringBuilder();
for(int i=0;i<list.size()-1;i++){
sb.append(list.get(i));
sb.append("->");
}
sb.append(list.get(list.size()-1));
res.add(sb.toString());
}
if(root.left!=null){
list.add(root.left.val);
findPath(root.left);
list.remove(list.size()-1);
}
if(root.right!=null){
list.add(root.right.val);
findPath(root.right);
list.remove(list.size()-1);
}
}
}
class Solution {
List<String> res=new ArrayList<>();
List<Integer> list=new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
if(root==null) return res;
findPath(root);
return res;
}
public void findPath(TreeNode root){
list.add(root.val);
if(root.left==null&&root.right==null){
StringBuilder sb=new StringBuilder();
for(int i=0;i<list.size()-1;i++){
sb.append(list.get(i));
sb.append("->");
}
sb.append(list.get(list.size()-1));
res.add(sb.toString());
}
if(root.left!=null){
findPath(root.left);
list.remove(list.size()-1);
}
if(root.right!=null){
findPath(root.right);
list.remove(list.size()-1);
}
}
}
9.相同的树
思路
其实就是两个左子树对比，两个右子树进行对比。然后确定好结束条件
①两个节点为空
②其中一个为空
③值不相等
最后就是一个后序遍历，因为你要知道是否相等，那么就需要先知道子树的结构是不是相同。这道题的思路和对称树相似。只是处理逻辑有点不同，主要是参数不同。
总结：后序遍历可以用于对比两棵树的结构。
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q==null) return true;
if(p!=null&&q==null) return false;
if(q!=null&&p==null) return false;
if(p.val!=q.val) return false;
boolean left=isSameTree(p.left,q.left);
boolean right=isSameTree(p.right,q.right);
boolean res=left&&right;
return res;
}
}
10.左叶子之和
递归法
思路
①只有父节点才能够判断左子节点是不是叶子节点，节点本身是不能够判断的，所以可以使用父节点提前判断
②终止条件是root==null的时候
③使用的是前中后序都可以，因为关键只是判断当前节点的左子节点是不是叶子节点
class Solution {
int sum=0;
public int sumOfLeftLeaves(TreeNode root) {
if(root==null) return sum;
tranverse(root);
return sum;
}
public void tranverse(TreeNode root){
if(root==null) return ;
tranverse(root.left);
tranverse(root.right);
if(root.left!=null&&root.left.left==null&&root.left.right==null){
sum+=root.left.val;
}
}
}
迭代法
思路
①与前序遍历处理方式一模一样，原因就是递归本质就是把对应节点压栈。
②心中有模板，把知识进行迁移。
class Solution {
int sum=0;
public int sumOfLeftLeaves(TreeNode root) {
if(root==null) return 0;
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.pop();
if(node.left!=null&&node.left.left==null&&node.left.right==null){
sum+=node.left.val;
}
if(node.right!=null) stack.push(node.right);
if(node.left!=null) stack.push(node.left);
}
return sum;
}
}
11.找树左下角的值
递归法
思路
①怎么确定是最后一行，怎么确定就是最左边的值。最后一行可以通过对比节点的深度来替换最大深度。最左边的值可以使用前序遍历的规律，遍历到的第一个叶子节点一定就是最左边的，也就是说，只要遍历到最左边的节点就能够改变深度，并且可以更新结果。如果不是当层最左边的节点是没办法参与更新结果的。
②处理逻辑使用了回溯来更新节点的深度
拓展
①这里的maxLeftLen可以用最小值代替
②从根节点开始深度len就是1，而不是0。
class Solution {
int maxLeftLen=0;
int maxVal=0;
int leftLen=1;
public int findBottomLeftValue(TreeNode root) {
traversal(root);
return maxVal;
}
public void traversal(TreeNode root){
if(root==null) return ;
if(root.left==null&&root.right==null){
if(leftLen>maxLeftLen){
maxLeftLen=leftLen;
maxVal=root.val;
}
return ;
}
leftLen++;
traversal(root.left);
leftLen--;
leftLen++;
traversal(root.right);
leftLen--;
}
}
迭代法
思路
①其实就是直接把进入队列的每一层遍历之前把第一个取出来，然后更新结果就可以了
总结：层序遍历可以解决找最左或者是最右的问题。
class Solution {
int maxVal=0;
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
TreeNode temp=queue.peek();
maxVal=temp.val;
while(size-->0){
TreeNode node=queue.poll();
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
}
return maxVal;
}
}
12.路径总和
递归法
思路
①需要返回对路径的总和判断，所以需要返回值boolean。
②结束条件有两个①叶子节点，并且sum最后减到0②叶子节点没有减到0；
③进入下一层递归的条件就是节点不能为空。并且总和需要进行回溯。
④如果是直接在第一个函数中进行递归，那么最后总和只需要去对比sum与最后的一个值大小
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null) return false;
return traversal(root,targetSum-root.val);
}
public boolean traversal(TreeNode root,int targetSum){
if(root.left==null&&root.right==null&&targetSum==0) return true;
if(root.left==null&&root.right==null) return false;
if(root.left!=null){
targetSum-=root.left.val;
if(traversal(root.left,targetSum)) return true;
targetSum+=root.left.val;
}
if(root.right!=null){
targetSum-=root.right.val;
if(traversal(root.right,targetSum)) return true;
targetSum+=root.right.val;
}
return false;
}
}
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null) return false;
if(root.left==null&&root.right==null&&targetSum==root.val) return true;
return hasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);
}
}
迭代法
思路
①与前序遍历的处理方式相同，但是这里需要保存的参数还有路径之和，保存方式与保存节点方式都是存入一个栈，跟随着栈走。新节点对应新路径之和，最后遍历到叶子节点的时候直接对比路径之和就可以了
总结：迭代法除了保存节点还能够保存与节点遍历同时更新的参数，方便最后进行对比。
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null) return false;
Stack<TreeNode> nodeStack=new Stack<>();
Stack<Integer> sumStack=new Stack<>();
nodeStack.push(root);
sumStack.push(root.val);
while(!nodeStack.isEmpty()){
TreeNode node=nodeStack.pop();
int sum=sumStack.pop();
if(node.left==null&&node.right==null&&sum==targetSum) return true;
if(node.right!=null){
nodeStack.push(node.right);
sumStack.push(sum+node.right.val);
}
if(node.left!=null){
nodeStack.push(node.left);
sumStack.push(sum+node.left.val);
}
}
return false;
}
}
路径总和2
思路
①递归法的思路基本一致，只不过需要把路径的值记录一下。
②需要注意的地方就是加入到结果集的时候一定要新创建一个arrayList不然就会共享一个list，后面回溯会改变这个list的值(只要是对象那么就要新建。注意一点回溯导致的对象修改问题)
class Solution {
List<List<Integer>> res=new ArrayList<>();
List<Integer> path=new ArrayList<>();
public void traversal(TreeNode root,int targetSum){
if(root.left==null&&root.right==null&&targetSum==0){
res.add(new ArrayList<>(path));
return;
}
if(root.left==null&&root.right==null) return ;
if(root.left!=null){
path.add(root.left.val);
traversal(root.left,targetSum-root.left.val);
path.remove(path.size()-1);
}
if(root.right!=null){
path.add(root.right.val);
traversal(root.right,targetSum-root.right.val);
path.remove(path.size()-1);
}
}
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if(root==null) return res;
path.add(root.val);
traversal(root,targetSum-root.val);
return res;
}
}
13.从中序到后序遍历构造二叉树
思路
①后序得根节点，中序得分割的左右子树进行继续递归。
②找到中序的分割index，然后左右递归。因为后序的左子树与中序的相同，所以可以利用这个特点来找到后序的左子树范围，中序能够通过分割找到左子树的范围以及个个数。后序左子树范围相当于就是left – left+左子树个数,右子树也是同样，left+左子树个数–postRihgt-1。中序呢就是left–index index+1–right因为这里执行的是左闭右开。
③判断结束条件(1)范围里面没有节点了<1
(2)只剩一个节点的时候直接返回一个新的节点。
④返回值就是节点，也可以说是根树的左子树和右子树。这样就能够通过当层构建树，然后递归让下面继续创建树范围。使用的是前序遍历。
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length==0||postorder.length==0) return null;
return buildTree1(inorder,0,inorder.length,
postorder,0,postorder.length);
}
public TreeNode buildTree1(int[] inorder,int inLeft,int inRight,
int[] postorder,int postLeft,int postRight){
if(inRight-inLeft<1) return null;
if(inRight-inLeft==1) return new TreeNode(inorder[inLeft]);
int rootVal=postorder[postRight-1];
int index=0;
for(int i=inLeft;i<inRight;i++){
if(inorder[i]==rootVal){
index=i;
break;
}
}
TreeNode root=new TreeNode(rootVal);
root.left=buildTree1(inorder,inLeft,index,
postorder,postLeft,postLeft+(index-inLeft));
root.right=buildTree1(inorder,index+1,inRight,
postorder,postLeft+(index-inLeft),postRight-1);
return root;
}
}
从前序到中序
思路
①基本一致
②但是需要注意要跳过的点是第一个，而且需要跳过第一个之后加上左子树个数才是下一段的前序序列分割位置。
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length<1||inorder.length<1) return null;
return buildTree1(preorder,0,preorder.length,
inorder,0,inorder.length);
}
public TreeNode buildTree1(int[] preorder,int preLeft,int preRight,
int[] inorder,int inLeft,int inRight){
if(inRight-inLeft<1) return null;
if(inRight-inLeft==1) return new TreeNode(inorder[inLeft]);
int rootVal=preorder[preLeft];
int index=0;
for(int i=inLeft;i<inRight;i++){
if(inorder[i]==rootVal){
index=i;
break;
}
}
TreeNode root=new TreeNode(rootVal);
root.left=buildTree1(preorder,preLeft+1,preLeft+1+(index-inLeft),
inorder,inLeft,index);
root.right=buildTree1(preorder,preLeft+1+(index-inLeft),preRight,
inorder,index+1,inRight);
return root;
}
}
14.最大二叉树
思路
①根据构建中序和后序遍历的二叉树，很明显之前是找到后序根节点，然后找中序的左子树和右子树的分割点，但是换到这里思路改一改只不过就是找到最大的点作为分割点。反而更简单了。
②这里还是用的是左闭右开，并且找到分割点之后，创建分割点的根节点，并且接着构造左子树和右子树。
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if(nums.length==0) return null;
return buildTree(nums,0,nums.length);
}
public TreeNode buildTree(int[] nums,int left,int right){
if(right-left<1) return null;
if(right-left==1) return new TreeNode(nums[left]);
int index=0;
int max=Integer.MIN_VALUE;
for(int i=left;i<right;i++){
if(nums[i]>max){
max=nums[i];
index=i;
}
}
TreeNode root=new TreeNode(max);
root.left=buildTree(nums,left,index);
root.right=buildTree(nums,index+1,right);
return root;
}
}
15.合并二叉树
递归法
思路
①本质就是遍历两棵树，然后合并两个节点，如果其中一个节点为空，那么直接就能返回另外一个节点
②一个节点为空，另一个不为空的情况，返回不空的节点回去是因为如果继续创建节点的问题就是另一个节点也是树，那么要继续递归就需要多上几个判断，需要特殊处理root1或者root2为空的情况，再往下创建新节点直到遍历完树。所以也可以直接返回另一个节点，也就是原本的树，也就能够直接拼上去。
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null) return root2;
if(root2==null) return root1;
TreeNode root=new TreeNode(root1.val+root2.val);
root.left=mergeTrees(root1.left,root2.left);
root.right=mergeTrees(root1.right,root2.right);
return root;
}
}
迭代法
思路
①遍历两棵树，分清楚情况，目标是把2直接合并到1
②情况：
1.两个树的左子树和右子树都不为空，直接进入队列继续
2.树1为空，树2不空，那么就给树1（左子节点或右子节点）直接复制
③需要注意如果是用栈处理，那么就要直到先进去应该是2，然后再进去1，那么出来的时候先出来的就是1。如果希望顺序一致可以使用队列来进行遍历处理。细节处理可以使用两个栈处理两个遍历会更清晰
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null) return root2;
if(root2==null) return root1;
Stack<TreeNode> stack=new Stack<>();
stack.push(root2);
stack.push(root1);
while(!stack.isEmpty()){
TreeNode node1=stack.peek();stack.pop();
TreeNode node2=stack.peek();stack.pop();
node1.val+=node2.val;
if(node1.left!=null&&node2.left!=null){
stack.push(node2.left);
stack.push(node1.left);
}
if(node1.right!=null&&node2.right!=null){
stack.push(node2.right);
stack.push(node1.right);
}
if(node1.left==null&&node2.left!=null){
node1.left=node2.left;
}
if(node1.right==null&&node2.right!=null){
node1.right=node2.right;
}
}
return root1;
}
}
16.二叉搜索树的搜索
递归法
思路
①二叉搜索树的特点就是左边的所有的节点一定是小于根节点的，右节点一定是大于根节点的。有了这个性质，二叉搜索树查找一个节点的方式就是有方向性的，可以根据具体搜索值的大小往左走或者往右走。
②结束条件就是root==null或者是找到对应的节点并且直接返回，而不需要去遍历另外一边
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root==null||root.val==val){
return root;
}
if(root.val>val){
return searchBST(root.left,val);
}
if(root.val<val){
return searchBST(root.right,val);
}
return null;
}
}
迭代法
思路
①二叉搜索树是有方向性的搜索，原因就是因为他的结构。走动方向完全可以根据val的大小和当前访问节点大小来决定走左边还是右边，如果相等可以直接返回
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root==null) return root;
while(root!=null){
if(root.val>val){
root=root.left;
}else if(root.val<val){
root=root.right;
}else{
return root;
}
}
return null;
}
}
17.验证二叉搜索树
思路
①使用中序遍历与二叉搜索树的特点，中序遍历一定是从小到大，只需要找一个变量记录这个数，如果发现有节点不符合立刻返回false。
②递归函数需要返回值通常是查找某个点或者是某个路径，又或者是创建树的时候
③需要注意这个地方最小值是是可以是integermin的，也就是说如果我们取的是integer_min就可能导致提前返回false，因为这个值并不足够小。
class Solution {
long max=Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root==null) return true;
boolean left=isValidBST(root.left);
if(root.val>max){
max=root.val;
}
else return false;
boolean right=isValidBST(root.right);
boolean res=left&&right;
return res;
}
}
迭代法
思路
①中序迭代模板，在点弹出来的时候把前一个与现在的节点进行大小比较，如果前一个>=cur的那么就结束循环。
②这里有两个条件的原因是，当根节点只有右节点的时候，那么stack就有可能出现空的情况，这个时候指针并不是空，所以仍然能够继续遍历执行。
class Solution {
public boolean isValidBST(TreeNode root) {
if(root==null) return true;
TreeNode cur=root;
TreeNode pre=null;
Stack<TreeNode> stack=new Stack<>();
while(cur!=null||!stack.isEmpty()){
if(cur!=null){
stack.push(cur);
cur=cur.left;
}else{
cur=stack.pop();
if(pre!=null&&cur.val<=pre.val){
return false;
}
pre=cur;
cur=cur.right;
}
}
return true;
}
}
18.二叉搜索树的最小绝对差
思路
①二叉搜索树+中序遍历等于有序数组，实际上就是请求有序数组的最小绝对差。直接求相邻的差即可
class Solution {
List<Integer> res=new ArrayList<>();
public void traversal(TreeNode root){
if(root==null) return ;
traversal(root.left);
res.add(root.val);
traversal(root.right);
}
public int getMinimumDifference(TreeNode root) {
int max=Integer.MAX_VALUE;
if(root==null) return 0;
traversal(root);
for(int i=1;i<res.size();i++){
if(Math.abs(res.get(i)-res.get(i-1))<max){
max=Math.abs(res.get(i)-res.get(i-1));
}
}
return max;
}
}
迭代法
class Solution {
public int getMinimumDifference(TreeNode root) {
if(root==null) return 0;
int max=Integer.MAX_VALUE;
List<Integer> res=new ArrayList<>();
Stack<TreeNode> stack=new Stack<>();
TreeNode cur=root;
while(cur!=null||!stack.isEmpty()){
if(cur!=null){
stack.push(cur);
cur=cur.left;
}else{
cur=stack.pop();
res.add(cur.val);
cur=cur.right;
}
}
for(int i=1;i<res.size();i++){
int distance=Math.abs(res.get(i)-res.get(i-1));
if(distance<max){
max=distance;
}
}
return max;
}
}
19.二叉搜索树的所有众数
递归法
思路
①第一种方案就是放进map，然后遍历map，找到最大总数的那几个就可以了。需要多次遍历。
②第二种方案就是通过中序+二叉搜索。因为按照小到大，所以相同的数基本挨在一起，可以使用pre和cur进行对比，并且计算频率。如果频率大于原来那个就可以更新结果集和新的频率，如果还有数值跟这个频率相等也能够加入结果集。关键就是频率更大的时候需要更新结果集。
class Solution {
Set<Integer> res=new HashSet<>();
TreeNode pre=null;
int count=0;
int max=Integer.MIN_VALUE;
public int[] findMode(TreeNode root) {
if(root==null) return new int[]{};
traversal(root);
int[] result=new int[res.size()];
int index=0;
for(int i:res){
result[index++]=i;
}
return result;
}
public void traversal(TreeNode root){
if(root==null) return;
traversal(root.left);
if(pre==null){
count=1;
}else if(pre.val==root.val){
count++;
}else{
count=1;
}
pre=root;
if(count==max){
res.add(root.val);
}
if(count>max){
max=count;
res=new HashSet<>();
res.add(root.val);
}
traversal(root.right);
}
}
暴力法
需要注意list取出来的是entry，我们需要比较的不是entry而是他们的值
class Solution {
Map<Integer,Integer> map=new HashMap<>();
public int[] findMode(TreeNode root) {
if(root==null) return new int[]{};
traversal(root);
List<Integer> res=new ArrayList<>();
List<Map.Entry<Integer,Integer>> list=map.entrySet().stream()
.sorted((x1,x2)->x2.getValue().compareTo(x1.getValue()))
.collect(Collectors.toList());
res.add(list.get(0).getKey());
for(int i=1;i<list.size();i++){
if(list.get(i).getValue()==list.get(i-1).getValue()) {
res.add(list.get(i).getKey());
}else{
break;
}
}
int index=0;
int[] result=new int[res.size()];
for(int i=0;i<res.size();i++){
result[i]=res.get(i);
}
return result;
}
void traversal(TreeNode root){
if(root==null) return;
map.put(root.val,map.getOrDefault(root.val,0)+1);
traversal(root.left);
traversal(root.right);
}
}
20.二叉树最近公共祖先
递归法
思路
①怎么知道子树下是否有对应的节点。怎么通知根节点是否存在要寻找的节点
可以通过返回对应节点。
②结束条件，遇到对应节点或者是null的时候直接返回
③处理逻辑
分多种情况。第一种是其中一棵树为空，另一棵不为空，那么就返回不为空的那个树得到的节点。另外一种就是左右子树遍历结果都不为空的情况，返回根节点，因为是后序遍历，从下到上，那么肯定就是找到最近的深度的节点就是最近的。如果都是空那么返回左子节点或者是右子节点都是可以的。
总结：这里遍历整棵树的原因是它不止找一个节点，有可能另外一个节点就在左边或者右边，所以需要遍历整棵树。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null||root==p||root==q) return root;
TreeNode left=lowestCommonAncestor(root.left,p,q);
TreeNode right=lowestCommonAncestor(root.right,p,q);
if(left!=null&&right!=null) return root;
if(left==null&&right!=null) return right;
if(right==null&&left!=null) return left;
return left;
}
}
21.二叉搜索树的最近公共祖先
思路
①二叉搜索树是有序的，也就是说，要找到的公共祖先一定是在，[p,q]范围里面。这样就好找了，我只要找到第一个在他们之间的范围的节点就是对应的最近公共祖先
②因为这里只是找一个节点所以可以直接返回，并不需要去到另外一边继续寻找
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return root;
if(p.val<root.val&&q.val<root.val){
if(root.left!=null){
return lowestCommonAncestor(root.left,p,q);
}
}
if(p.val>root.val&&q.val>root.val){
if(root.right!=null){
return lowestCommonAncestor(root.right,p,q);
}
}
return root;
}
}
迭代法（在空间复杂度上面更优）
思路
①最近公共祖先有三种情况
p在root左子树或者右子树
p刚好就是root.
②而且是二叉搜索树，也就是说，只要符合p和q，root在他们的范围里面的第一个点就可以了，一定是等于或者是小于，或者是>=。p和q两个都占，p.val<=root.val<=q.val相反也是可以的。也就是直接排除掉，p和q同时在root的左边或者是右边的情况
总结：这种while的迭代模板通常用在二叉搜索树上，因为可以用于比较大小确定路径的走向
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return root;
while(root!=null){
if(root.val>p.val&&root.val>q.val){
root=root.left;
}else if(root.val<p.val&&root.val<q.val){
root=root.right;
}else{
break;
}
}
return root;
}
}
22.二叉搜索树的插入
递归法
思路
①利用左小右大的特点根据val与root的比较找到对应的空的位置。并且插入。
②这里返回了节点，相当于就是返回了修改之后的节点，或者是返回了创建的新节点。
③如果没有返回值，需要记录parent节点但是思路基本上是一致的
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null) return new TreeNode(val);
if(root.val>val) root.left=insertIntoBST(root.left,val);
if(root.val<val) root.right=insertIntoBST(root.right,val);
return root;
}
}
class Solution {
TreeNode parent;
public void traversal(TreeNode root,int val){
if(root==null){
if(parent.val>val) parent.left=new TreeNode(val);
else parent.right=new TreeNode(val);
return ;
}
parent=root;
if(root.val>val) traversal(root.left,val);
if(root.val<val) traversal(root.right,val);
}
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null) return new TreeNode(val);
traversal(root,val);
return root;
}
}
迭代法
思路
①二叉搜索的套路，但是一定要用if和else只能走一条路，如果是两个if都判断成功就可能会出现空指针异常，原因是前面已经进行了cur=cur.left转移了cur的访问位置，如果再次cur=cur.right可能现在的cur已经是空节点了
②模板+记录parent，找到空节点位置然后插入即可
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null) return new TreeNode(val);
TreeNode parent=root;
TreeNode cur=root;
while(cur!=null){
parent=cur;
if(cur.val>val) cur=cur.left;
else cur=cur.right;
}
if(parent.val>val) parent.left=new TreeNode(val);
else parent.right=new TreeNode(val);
return root;
}
}
23.删除二叉搜索树的节点
递归法
思路
①需要返回值，返回修改之后的节点。
②删除逻辑有四种情况，第一种就是左右子树都是空，那么这个时候直接返回null回去，接上父节点。第二种就是左子树空，右子树不空，那么返回右子树接上父节点，不要当前节点，第三种就是前面那种反过来。最后一种就是左右子树都不是空的情况，那么就把左子树放到右子树的最左边（直接遍历过去），接着返回右子树接上。
③遍历需要用到搜索树的特点，只搜索一边。
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null) return root;
if(root.val==key){
if(root.left==null&&root.right==null) return null;
else if(root.left!=null&&root.right==null) return root.left;
else if (root.right!=null&&root.left==null) return root.right;
else{
TreeNode temp=root.right;
while(temp.left!=null){
temp=temp.left;
}
temp.left=root.left;
return root.right;
}
}
if(root.val>key) root.left=deleteNode(root.left,key);
if(root.val<key) root.right=deleteNode(root.right,key);
return root;
}
}
迭代法
思路
①和上面一样
②需要注意，这里一定要把四种情况全部讨论清除。
class Solution {
public TreeNode delete(TreeNode root){
if(root==null||(root.left==null&&root.right==null)) return null;
if(root.right==null&&root.left!=null) return root.left;
TreeNode temp=root.right;
while(temp.left!=null){
temp=temp.left;
}
temp.left=root.left;
return root.right;
}
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null) return root;
TreeNode pre=null;
TreeNode cur=root;
while(cur!=null){
if(cur.val==key) break;
pre=cur;
if(cur.val>key) cur=cur.left;
else if(cur.val<key) cur=cur.right;
}
if(pre==null){
return delete(cur);
}
if(pre.left!=null&&pre.left.val==key){
pre.left=delete(cur);
}
if(pre.right!=null&&pre.right.val==key){
pre.right=delete(cur);
}
return root;
}
}
24.修剪二叉树
递归法
思路
①找到这个不是这个范围的节点直接删除？
很明显并不是，找到这个节点之后，如果比范围小，那么可以去右子树看看（可能存在范围内的节点）
并且需要的就是这些范围内的节点，不是范围内的就去掉。
②怎么过滤掉这些点？
不要单从一棵树上看，最好就是局部看一下，只要发现不符合规则的节点，那么就去到可能符合规则的位置看有没有能够顶替的节点并进行返回，其实就已经过滤前面节点，它返回的是后面符合条件的树或者是节点
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root==null) return root;
if(root.val<low){
TreeNode right=trimBST(root.right,low,high);
return right;
}
if(root.val>high){
TreeNode left=trimBST(root.left,low,high);
return left;
}
root.left=trimBST(root.left,low,high);
root.right=trimBST(root.right,low,high);
return root;
}
}
25.有序数组转换成二叉搜索树
递归法
思路
①有序数组，可以每次都取中点作为对应的根节点，原因就是左子树和右子树节点范围一定包括了中点。找到中点创建节点，然后递归继续创建，并且给左子树和右子树赋值，返回创建后的节点.
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length==0) return null;
return buildTree(nums,0,nums.length-1);
}
public TreeNode buildTree(int[] nums,int left,int right){
if(left>right) return null;
int mid=left+((right-left)/2);
TreeNode root=new TreeNode(nums[mid]);
root.left=buildTree(nums,left,mid-1);
root.right=buildTree(nums,mid+1,right);
return root;
}
}
迭代法
思路
①其实和递归法相似，但是不同的是这里使用了3个队列，一个保存节点，一个保存左边界，一个保存右边界。最重要的是需要先创建节点放入队列中，等待遍历的时候再处理中间节点的值。然后就是根据mid取值，判断是否需要处理左子树和右子树，如果需要再加入到队列，不需要的话就不进行处理
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length==0) return null;
Queue<TreeNode> nodeQue=new LinkedList<>();
Queue<Integer> leftQue=new LinkedList<>();
Queue<Integer> rightQue=new LinkedList<>();
leftQue.offer(0);
rightQue.offer(nums.length-1);
TreeNode root=new TreeNode();
nodeQue.offer(root);
while(!nodeQue.isEmpty()){
TreeNode node=nodeQue.poll();
int left=leftQue.poll();
int right=rightQue.poll();
int mid=left+(right-left)/2;
node.val=nums[mid];
if(left<=mid-1){
node.left=new TreeNode(0);
nodeQue.offer(node.left);
leftQue.offer(left);
rightQue.offer(mid-1);
}
if(right>=mid+1){
node.right=new TreeNode(0);
nodeQue.offer(node.right);
leftQue.offer(mid+1);
rightQue.offer(right);
}
}
return root;
}
}
26.把二叉搜索树换为累加树
递归法
思路
①二叉树有序，利用有序，那么只要计算那些比root.val大的所有其他节点的和包括root自身。那么倒过来就是从大到小的排序，比最大val大的只有它自己，那么从最后累加过来就可以了。
class Solution {
int sum=0;
public TreeNode convertBST(TreeNode root) {
if(root==null) return null;
convertBST(root.right);
sum+=root.val;
root.val=sum;
convertBST(root.left);
return root;
}
}
迭代法
思路
①同样是中序遍历，只需要在弹出的时候进行操作
②不需要提前把root放进stack里面，原因是它会根据cur是否为null才放进stack最后才开始遍历。
class Solution {
public TreeNode convertBST(TreeNode root) {
if(root==null) return null;
TreeNode cur=root;
Stack<TreeNode> stack=new Stack<>();
int sum=0;
while(cur!=null||!stack.isEmpty()){
if(cur!=null){
stack.push(cur);
cur=cur.right;
}else{
cur=stack.pop();
sum+=cur.val;
cur.val=sum;
cur=cur.left;
}
}
return root;
}
}
|