找到中序遍历二叉树下一个节点
分析二叉树的下一个节点，一共有以下情况：
1.二叉树为空，则返回空；
2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；
3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。代码如下
//8,6,10,5,7,9,11
/*
* 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
* 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
*/
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode==null)
return null;
if(pNode.right!=null){//如果有右子树，找右子树的最左节点
TreeLinkNode p=pNode.right;
while(p.left!=null){
p=p.left;
}
return p;
}
while(pNode.next!=null){//没右子树，则找第一个当前结点是父节点左孩子的节点
if(pNode.next.left==pNode)//节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历
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;
}
}
之字形打印二叉树
利用栈后进先出的特性，两个栈一个存奇数层节点，一个存偶数层节点
/*
* 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，
* 第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
*/
//{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;
}
反转链表
方法一
//反转链表
ListNode reverseNode(ListNode phead){
ListNode preverhead=null;//保存翻转后的头结点 是原始链表的尾结点
ListNode pnode=phead;//当前节点
ListNode pprev=null;//当前节点的左一个节点
while(pnode!=null){
ListNode pnext=pnode.next;//当前节点的下一个节点
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;
}
合并两个有序链表
方法一 递归
//合并两个有序链表
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;
}
方法二 新建一个头结点
//新建一个头结点的方式 合并有序链表
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;
}
方法三 先赋值第一个节点
//先赋值第一个节点
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;
}
网友评论