找到中序遍歷二叉樹下一個(gè)節(jié)點(diǎn)
分析二叉樹的下一個(gè)節(jié)點(diǎn)，一共有以下情況：
1.二叉樹為空焚鹊，則返回空腕够；
2.節(jié)點(diǎn)右孩子存在逊脯，則設(shè)置一個(gè)指針從該節(jié)點(diǎn)的右孩子出發(fā)优质，一直沿著指向左子結(jié)點(diǎn)的指針找到的葉子節(jié)點(diǎn)即為下一個(gè)節(jié)點(diǎn)；
3.節(jié)點(diǎn)不是根節(jié)點(diǎn)军洼。如果該節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子巩螃，則返回父節(jié)點(diǎn)；否則繼續(xù)向上遍歷其父節(jié)點(diǎn)的父節(jié)點(diǎn)匕争，重復(fù)之前的判斷避乏，返回結(jié)果。代碼如下
//8,6,10,5,7,9,11
/*
* 給定一個(gè)二叉樹和其中的一個(gè)結(jié)點(diǎn)甘桑，請找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回拍皮。
* 注意，樹中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)跑杭，同時(shí)包含指向父結(jié)點(diǎn)的指針春缕。
*/
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode==null)
return null;
if(pNode.right!=null){//如果有右子樹，找右子樹的最左節(jié)點(diǎn)
TreeLinkNode p=pNode.right;
while(p.left!=null){
p=p.left;
}
return p;
}
while(pNode.next!=null){//沒右子樹艘蹋，則找第一個(gè)當(dāng)前結(jié)點(diǎn)是父節(jié)點(diǎn)左孩子的節(jié)點(diǎn)
if(pNode.next.left==pNode)//節(jié)點(diǎn)不是根節(jié)點(diǎn)。如果該節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子票灰，則返回父節(jié)點(diǎn)女阀；否則繼續(xù)向上遍歷
return pNode.next;
pNode=pNode.next;
}
return null;
}
class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
之字形打印二叉樹
利用棧后進(jìn)先出的特性，兩個(gè)棧一個(gè)存奇數(shù)層節(jié)點(diǎn)屑迂，一個(gè)存偶數(shù)層節(jié)點(diǎn)
/*
* 請實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹浸策，即第一行按照從左到右的順序打印，
* 第二層按照從右至左的順序打印惹盼，第三行按照從左到右的順序打印庸汗，其他行以此類推。
*/
//{8,6,10,5,7,9,11}
public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> all=new ArrayList<ArrayList<Integer>>();
int layer=1;
Stack<TreeNode> s1=new Stack<TreeNode>();
Stack<TreeNode> s2=new Stack<TreeNode>();
s1.push(pRoot);
while(!s1.empty()||!s2.empty()){
if(layer%2!=0){
ArrayList<Integer> temp=new ArrayList<Integer>();
while(!s1.empty()){
TreeNode node=s1.pop();
if(node!=null){
temp.add(node.val);
System.out.print(node.val + " ");
s2.push(node.left);
s2.push(node.right);
}
}
if(!temp.isEmpty()){
all.add(temp);
layer++;
System.out.println();
}
}else{
ArrayList<Integer> temp=new ArrayList<Integer>();
while(!s2.empty()){
TreeNode node=s2.pop();
if(node!=null){
temp.add(node.val);
System.out.print(node.val + " ");
s1.push(node.right);
s1.push(node.left);
}
}
if(!temp.isEmpty()){
all.add(temp);
layer++;
System.out.println();
}
}
}
return all;
}
多行打印二叉樹
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
if(pRoot==null)
return result;
Queue<TreeNode> layer=new LinkedList<>();
ArrayList<Integer> list=new ArrayList<Integer>();
layer.add(pRoot);
int start=0,end=1;
while(!layer.isEmpty()){
TreeNode cur=layer.remove();
list.add(cur.val);
start++;
if(cur.left!=null)
layer.add(cur.left);
if(cur.right!=null)
layer.add(cur.right);
if(start==end){
end=layer.size();
start=0;
result.add(list);
list=new ArrayList<>();
}
}
return result;
}
反轉(zhuǎn)鏈表
方法一
//反轉(zhuǎn)鏈表
ListNode reverseNode(ListNode phead){
ListNode preverhead=null;//保存翻轉(zhuǎn)后的頭結(jié)點(diǎn) 是原始鏈表的尾結(jié)點(diǎn)
ListNode pnode=phead;//當(dāng)前節(jié)點(diǎn)
ListNode pprev=null;//當(dāng)前節(jié)點(diǎn)的左一個(gè)節(jié)點(diǎn)
while(pnode!=null){
ListNode pnext=pnode.next;//當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
if(pnext==null)
preverhead=pnode;
pnode.next=pprev;
pprev=pnode;
pnode=pnext;
}
return preverhead;
}
方法二
public ListNode ReverseList(ListNode head) {
if(head==null)
return null;
ListNode pre=null;
ListNode next=null;
while(head!=null){
next=head.next;
head.next=pre;
pre=head;
head=next;
}
return pre;
}
合并兩個(gè)有序鏈表
方法一 遞歸
//合并兩個(gè)有序鏈表
public ListNode merge(ListNode node1,ListNode node2){
if(node1==null)
return node2;
else if(node2==null)
return node1;
ListNode p=null;
if(node1.val<node2.val){
p=node1;
p.next=merge(node1.next,node2);
}else{
p=node2;
p.next=merge(node2.next,node1);
}
return p;
}
方法二 新建一個(gè)頭結(jié)點(diǎn)
//新建一個(gè)頭結(jié)點(diǎn)的方式 合并有序鏈表
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode head=new ListNode(-1);
head.next=null;
ListNode root=head;
while(list1!=null&&list2!=null){
if(list1.val<list2.val){
head.next=list1;
head=list1;
list1=list1.next;
}else{
head.next=list2;
head=list2;
list2=list2.next;
}
}
if(list1!=null)
head.next=list1;
if(list2!=null)
head.next=list2;
return root.next;
}
方法三 先賦值第一個(gè)節(jié)點(diǎn)
//先賦值第一個(gè)節(jié)點(diǎn)
public ListNode Merge2(ListNode list1,ListNode list2) {
ListNode head=null;
if(list1.val<=list2.val){
head=list1;
list1=list1.next;
}else{
head=list2;
list2=list2.next;
}
ListNode p=head;
while(list1!=null&&list2!=null){
if(list1.val<list2.val){
p.next=list1;
list1=list1.next;
}else{
p.next=list2;
list2=list2.next;
}
p=p.next;
}
if(list1!=null)
p.next=list1;
if(list2!=null)
p.next=list2;
return head;
}
