遍历字符串2.从第一个元素开始,如果有相同的就替换为""也就是没有

二.二叉树相关Oj题

1.二叉树的遍历

import java.util.*;
class TreeNode {TreeNode left;TreeNode right;char  val;TreeNode(char val) {this.val = val;}
}// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void inorder(TreeNode root) {if (root == null) return;inorder(root.left);System.out.print(root.val + " ");inorder(root.right);}public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str = in.nextLine();TreeNode root = creat(str);inorder(root);System.out.println();}}public static int i = 0;public static TreeNode creat(String ret) {TreeNode root =null;if (ret.charAt(i) != '#') {root=new TreeNode(ret.charAt(i));i++;root.left = creat(ret);root.right = creat(ret);} else {i++;}return root;}}

这里我出现了一些问题

在创建二叉树这一步,我先入为主直接初始化根,先不说没有考虑到第一个节点就是空的,也就是这棵树就是空树.也没有考虑到假如树的分节点是空的,进入递归,直接创建了一个内容是#的树而不是返回空.逻辑出错

最好的方法就是初始化先是null.判断是否为#.是就初始化,并i++.进入left.或者就是null并i+=

往后遍历

2.二叉树分层遍历

这里我们考虑到用队列.先进先出,底层用顺序表也就是数组存放每一层

遍历树.判断是否为空,不是就是放入他的左子树和右子树.并打印他,

如果是空,就不打印

这样从左向右打印

class Solution {public List> levelOrder(TreeNode root) {List> lists=new ArrayList<>();if(root==null) return lists;Queue queue=new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){List list=new ArrayList<>();int size=queue.size();//求队列长度没有length公式只有大小的while(size!=0){TreeNode cur=queue.poll();list.add(cur.val);if(cur.left!=null){queue.offer(cur.left);} if(cur.right!=null){queue.offer(cur.right);}size--;}lists.add(list);}return lists;}
}

注意队列的长度公式.只有里面有多少元素 的公式也就是 queue.size()

这道题怎么样分层

就是求每一次循环得到的队列长度,然后循环放入

并且每次放入顺序表里,都会弹出.这样保证上一层的空了

这种情况,遇到最后一组,会显示还有元素,就继续进入循环,但是因为是空的,所以不放元素,但是还是一组表,就会显示多一层

所以还是得分开进行判断放元素

这道题还有很多问法

1.求二叉树的左视图,其实就是链表的每组数组的第一个元素

2.求二叉树的宽度,其实就是数组最长的,

三.二叉树的最近公共祖先

1.思路一

如果给定的树是一颗二叉搜索树

根节点的左子树都比根小

根节点的右子树都比根大

根据中序遍历 : 左子树-根-右子树

我们可以思考

就按根节点来想.如果

1.p是root或者q是root

2.如果p的值和q的值都小于root.那么就说明公共祖先都在root的左树

那就说明公共祖先是在root的左树中

3.如果p的值和q的值都大于root.那么就说明公共祖先都在root的右树

那就说明公共祖先是root的右树

4.如果一个大于根节点另外一个小于根节点,就说明一个在左子树,一个在右子树

那么公共祖先就是root

那么我们可以往后递归,再对root,left和root.right进行判断递归

直到找到满足条件

那么我们再发散一下,如果他只是一颗普通的树呢

那就分别在左子树和右子树找到p或者q,如果能在左子树或者右子树找到那就返回找到的节点

但是如果左子树和右子树都找到了.那就返回根节点

如果都没有就返回null

然后再发散一下

递归根节点,传递的p和q不变

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null) return null;if(p==root||q==root) return root;TreeNode curLeft=lowestCommonAncestor( root.left, p, q);TreeNode curright=lowestCommonAncestor( root.right, p, q);if(curLeft!=null&&curright==null){return curLeft;}if(curLeft==null&&curright!=null){return curright;}if(curLeft!=null&&curright!=null){return root;}return null;}
}

先判断是否是空的,再判断是否找到,如果找不到就开始往下递归.,如果一边有一边没有,就返回一边的.如果两边都有,就说明在两边就直接返回这个节点,如果两边都没有,就返回null

递归回来,

递归的思想我觉得就是先大问题,然后通过小问题判断细节,就搞定.

2.思路2

假设这颗二叉树是孩子双亲表示法表示的

因为都知道上一颗连接他的是谁,回溯过去,就跟链表求交点的题目一样的做法

先存储节点的对应的父节点回溯过去存储在相应链表里

但是这道题是孩子表示法表示,并没有双亲节点

因为栈可以依次存储,并先进后出,依次从后往前吐出来

第一步.我们可以用两个栈存储路径

第二步.求栈的大小

第三步,让栈中多的元素出差值个元素

第四步开始出栈,直到栈顶元素相同,此时就是公共祖先,

框架搭好了

但是还是有疑惑.我们如何找根节点到指定节点的路径呢

所以这里我们需要建立一个路径的方法.

这里我的思路就是先判断是否为空,返回假

然后直接把root压入栈内,

然后判断是否为相同,就直接返回真

如果都不相同.就开始找子树或者右树

如果在一个节点的右树找到,那么在他的左树所有压进去的节点都会弹出来.

并会返回false.就开始向上递归.

因为左边没有相同的额节点的时候,就会弹出,每回溯一次都会弹出一次,直到回到那个节点,

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null) return null;Stack s1=new Stack<>();Stack s2=new Stack<>();path(root,p,s1);path(root,q,s2);int size1=s1.size();int size2=s2.size();int size=0;if(size1>size2){size=size1-size2;while(size!=0){s1.pop();size--;}}else{size=size2-size1;while(size!=0){s2.pop();size--;}}while(!s1.isEmpty()){if(s1.peek()==s2.peek()){return s1.peek();}s1.pop();s2.pop();}return null;}boolean path(TreeNode root,TreeNode p,Stack s){if(root==null||p==null) return false;s.push(root);if(root==p) return true;boolean flg=path(root.left,p,s);if(flg) return true;flg=path(root.right,p,s);if(flg) return true;s.pop();return false;}

四.将二叉搜索树转化为有序链表

我的思路就是一边排序一边修改指向