假设二叉树用二叉链表存储,试编写算法,求二叉树的高度,基于二叉链表写出层序遍历二叉树的算法
题目一
链表题——反转链表
根据单链表的头节点头来返回反转后的链表
具体题目如下
解法
/** *单链表的定义。*公共类ListNode { * int val * ListNode next * ListNode(){ } * ListNode(int val){ this。val=val} * ListNode(int val，list node next){ this。val=valthis . next=next } * } */class Solution { public ListNode reverse list(ListNode head){ ListNode pre，cur，nxtpre=nullcur=头；nxt=头；而(cur！=null){ NXT=cur。接下来；cur.next=prepre=curcur=nxt }返回pre}}
题目二
链表题——反转链表
按照一定数量的节点来进行反转并返回反转之后的链表
具体题目如下
解法
/** *单链表的定义。*公共类ListNode { * int val * ListNode next * ListNode(){ } * ListNode(int val){ this。val=val} * ListNode(int val，list node next){ this。val=valthis . next=next } * } */class Solution { public ListNode reverse group(ListNode head，int k) { if (head==null)返回nullListNode a，b；a=b=头；for(int I=0；我k；i ) { if (b==null)返回头；b=b .下一个；} ListNode newHead=reverse(a，b)；a . next=反转组(b，k)；返回new head } list node reverse(list node a，ListNode b) { ListNode pre，cur，NXT pre=null cur=a；NXT=a；而(cur！=b){ NXT=cur。接下来；cur.next=prepre=curcur=nxt }返回pre}}
题目三
链表题——回文链表
根据单链表的头节点头来判断该链表是否是回文链表，并返回结果
具体题目如下
解法：后序遍历与左边的比较
/** *单链表的定义。*公共类ListNode { * int val * ListNode next * ListNode(){ } * ListNode(int val){ this。val=val} * ListNode(int val，list node next){ this。val=valthis . next=next } * } */class Solution { ListNode left；聚氨酯
blic boolean isPalindrome(ListNode head) { left = head; return traverse(head); } boolean traverse(ListNode right){ if (right == null) return true; boolean res = traverse(right.next); res = res && (right.val == left.val); left = left.next; return res; }}
题目四
二叉树题——翻转二叉树
根据所给的二叉树根节点root来翻转此二叉树，并返回翻转后的二叉树根节点
具体题目如下
解法
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public TreeNode invertTree(TreeNode root) { if(root==null){ return null; } TreeNode lf = invertTree(root.left); TreeNode rg = invertTree(root.right); root.left = rg; root.right = lf; return root; }}题目五
二叉树题——填充节点
给定一个完美二叉树，填充该二叉树每个节点的下一个右侧节点指针
具体题目如下
解法
/*// Definition for a Node.class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; }};*/ class Solution { public Node connect(Node root) { if(root==null) return null; method(root.left,root.right); return root; } public void method(Node left,Node right){ if (left == null right == null) { return; } left.next = right; method(left.left,left.right); method(right.left,right.right); method(left.right,right.left); }}题目六
二叉树链表题——将二叉树展开为链表
根据给定的二叉树根节点root，将此二叉树展开为单链表
具体题目如下
解法
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public void flatten(TreeNode root) { if (root == null) return; flatten(root.left); flatten(root.right); TreeNode left = root.left; TreeNode right = root.right; root.left = null; root.right = left; TreeNode p = root; while (p.right != null) { p = p.right; } p.right = right; }}到此这篇关于剑指Offer之Java算法习题精讲链表与二叉树专项训练的文章就介绍到这了,更多相关Java 链表内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。