剑指offer题解4

剑指offer题解4

14 翻转链表15 合并有序链表16 树的子结构17 二叉树的镜像

14 翻转链表

输入一个链表，反转链表后，输出新链表的表头。

分析:采用头插法,遍历原链表,将每一个节点都插到目标链表的头部

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode ReverseList(ListNode head) { ListNode dummy=new ListNode(0); while(head!=null){ ListNode curr=dummy.next; dummy.next=head; head=head.next; dummy.next.next=curr; } return dummy.next; } }

15 合并有序链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

分析:遍历,直接归并;递归

//循环 public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { ListNode res=new ListNode(0); ListNode curr=res; while(list1!=null&&list2!=null){ //根据大小移动指针 if(list1.val<=list2.val){ curr.next=list1; list1=list1.next; }else { curr.next=list2; list2=list2.next; } curr=curr.next; } //当有一方为null时,直接吧另一个添加在尾部 curr.next= list1==null?list2:list1; return res.next; } } //递归 public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null){ return list2; }else if(list2==null){ return list1; } if(list1.val<list2.val){ list1.next=Merge(list1.next,list2); return list1; }else{ list2.next=Merge(list1,list2.next); return list2; } } }

16 树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

分析:考察分治思想 树b是树a的子树,那么当遇到一个节点m与树b的根节点相同时,就开始判断是否是子树:b的左子树是m的左子树,b的右子树是m的右子树

public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { if(root1==null||root2==null){ return false; } //首先判断是否是子树,然后走左子树,然后走右子树 return isSubTree(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2); } public boolean isSubTree(TreeNode root1,TreeNode root2){ //如果root2==null,说明root2已经走到了叶子节点,不必判断root1,直接返回true if(root2==null){ return true; } //root2!=null,如果root1==null,说明root1已经到了叶子节点而root2还没有到叶子节点 //或者节点的值不相等,返回false if(root1==null||root1.val!=root2.val){ return false; } return isSubTree(root1.left,root2.left)&&isSubTree(root1.right,root2.right); } }

17 二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

分析:递归即可,将左右自子树交换,然后对左右子树分别再进行镜像

public class Solution { public void Mirror(TreeNode root) { if(root!=null){ //交换 TreeNode left=root.left; root.left=root.right; root.right=left; //递归 Mirror(root.left); Mirror(root.right); } } }