一、二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
基本思路：
我们在二叉树的基本操作中已经实现了一次二叉树的层序遍历，但我们是直接进行打印，这里我们想把二叉树的每一层的结点放入list中，我们还是采用queue来存储每一个结点，然后每次循环时，记录一下每层的元素个数，然后将每一层的结点放入list中，每次循环结束后将list放入list中。
public list> levelorder(treenode root) {
//层序遍历
list> list = new arraylist<>();
if(root == null) {
return list;
}
queue qu = new linkedlist<>();
qu.offer(root);
while(!qu.isempty()) {
list list1 = new arraylist<>();
int sz = qu.size();
while(sz > 0) {
treenode node = qu.poll();
sz--;
list1.add(node.val);
if(node.left != null) {
qu.offer(node.left);
}
if(node.right != null) {
qu.offer(node.right);
}
}
list.add(list1);
}
return list;
}
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 t 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
基本思路：
我们定义两个站，将根节点到p,q的路径全部放入两个栈中，就有点链表交点的感觉了，然后判断两个栈的大小，把多余元素先弹出，然后一起判断，直到相同结点为止。
public treenode lowestcommonancestor(treenode root, treenode p, treenode q) {
stack stack1 = new stack<>();
findpath(root,p,stack1);
stack stack2 = new stack<>();
findpath(root,q,stack2);
int sz1 = stack1.size();
int sz2 = stack2.size();
if(sz1 > sz2) {
int sz = math.abs(sz1 - sz2);
while(sz > 0) {
stack1.pop();
sz--;
}
}else {
int sz = math.abs(sz1 - sz2);
while(sz > 0) {
stack2.pop();
sz--;
}
}
while (stack1.peek() != stack2.peek()) {
stack1.pop();
stack2.pop();
}
return stack1.peek();
}
public boolean findpath(treenode root, treenode node,stack stack) {
if(root == null || node == null){
return false;
}
stack.push(root);
if(root == node) {
return true;
}
boolean f1 = findpath(root.left,node,stack);
if(f1 == true) {
return true;
}
boolean f2 = findpath(root.right,node,stack);
if(f2 == true) {
return true;
}
stack.pop();
return false;
}
这样显然可以达到目的，但是时间复杂度有点高，我们能不能想一个时间复杂度比较低的解法。
我们先来认识一下：什么是二叉搜索树(二叉排序树）
二叉搜索树中，任何一结点的左节点总是小于该结点，右节点总是大于该节点。
那我们最近公共祖先总共有几种情况呢？分为三种情况，1：p,q在同一位置 2：p,q在某一结点的两侧 3：p,q在某一结点的同一侧。
public treenode lowestcommonancestor(treenode root, treenode p, treenode q) {
if(root == null || p == null || q == null) {
return null;
}
if(p == root || q == root) {
return root;
}
treenode left = lowestcommonancestor(root.left,p,q);
treenode right = lowestcommonancestor(root.right,p,q);
if(left != null && right != null) {
return root;
} else if(left == null) {
return right;
}else if(right == null) {
return left;
}else {
return null;
}
}
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： abc##de#g##f### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
我们可以看到这是一道较难题。
思路分析：
之前我们不是说过要想构建一个二叉树，必须直到中序遍历的结果，这道题只给了先序遍历的结果，能构建出来二叉树吗？我们可以发现题中给了空格的位置，那么我们就可以构建出来了，构建出来之后对二叉树进行中序遍历即可。因为先序遍历给我们的是字符串，我们要想取每一个结点，就得获取字符串的每一个字符，这里我们定义一个静态成员变量j记录先序遍历的每一个结点。
import java.util.scanner;
class treenode {
char val;
treenode left;
treenode right;
public treenode(char val) {
this.val = val;
}
}
public class main {
public static void main(string[] args) {
scanner in = new scanner(system.in);
while (in.hasnextline()) {
string str = in.nextline();
treenode root = presort(str);
inorder(root);
system.out.println();
}
}
public static void inorder(treenode root) {
if(root == null) {
return;
}
inorder(root.left);
system.out.print(root.val " ");
inorder(root.right);
}
public static int j = 0;
public static treenode presort(string str) {
treenode root = null;
if(j < str.length()) {
char c = str.charat(j);
if(c != '#') {
root = new treenode(c);
j ;
root.left = presort(str);
root.right = presort(str);
}else {
j ;
}
}
return root;
}
}
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的treenode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出
思路分析：
题目要求我们将一棵二叉搜索树转换为一个双链表，二叉树的left为链表的前驱，二叉树的right为链表的后驱。
这里我们采取前序遍历，在遍历到每一个结点的时候，改变结点的指向，将left指向前一结点,right指向后一结点。
改变指向后那怎么找到头节点呢，因为我们的根节点已经成为链表中的某一结点，接下来我们将根节点往前遍历，直到.left为空为止，该节点就为头节点。
我们发现执行上面的代码就可以达到目的，但我们发现刚开始pre为空，没有right如果执行的话就会出现空指针异常，所以我们在执行时应该判断一下pre是否为空。
public treenode convert(treenode prootoftree) {
if(prootoftree == null) {
return null;
}
createlist(prootoftree);
while(prootoftree.left != null) {
prootoftree = prootoftree.left;
}
return prootoftree;
}
treenode pre = null;
public void createlist(treenode root) {
if(root == null) {
return;
}
createlist(root.left);
root.left = pre;
if(pre != null) {
pre.right = root;
}
pre = root;
createlist(root.right);
}