目录
1.链表回文结构
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
if(A == null){
return false;
}
// write code here
ListNode fast = A;
ListNode slow = A;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode cur = slow.next;
while(cur != null){
ListNode curN = cur.next;
cur.next = slow;
slow = cur;
cur = curN;
}
while(A != slow){
if(A.val != slow.val){
return false;
}
if(A.next == slow){
return true;
}
A= A.next;
slow = slow.next;
}
return true;
}
}2.相交链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pl = headA;
ListNode ps = headB;
int lenA = 0;
int lenB = 0;
//计算长度
while(pl != null){
lenA++;
pl = pl.next;
}
while(ps != null){
lenB++;
ps = ps.next;
}
pl = headA;
ps = headB;
//计算两个链表的差值
int len = lenA - lenB;
if(len < 0){
pl = headB;
ps = headA;
len = lenB - lenA;
}
while(len != 0){
pl = pl.next;
len--;
}
while(pl != ps){
pl = pl.next;
ps = ps.next;
}
if(pl == null){
return null;
}
return pl;
}
}3.环形链表
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow ){
return true;
}
}
return false;
}
}4.返回相遇点的值
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow ){
break;
}
}
if(fast == null || fast.next = null){
return false;
}
while(fast != slow){
slow = head;
slow = slow.next;
fast = fast.next;
}
return slow;
}
}5.二叉树的前序遍历
/**
* 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 List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
list.add(root.val);
List<Integer> leftTree = preorderTraversal(root.left);
list.addAll(leftTree);
List<Integer> rightTree = preorderTraversal(root.right);
list.addAll(rightTree);
return list;
}
}6.相同的树力扣
设p有m个节点，q有n个节点，则时间复杂度为Q（m,n）的最小值。
/**
* 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 boolean isSameTree(TreeNode p, TreeNode q) {
//先判断两颗树的结构是否相同
if(p !=null && q == null || p == null && q != null){
return false;
}
//上述语句入果没有执行说明两个语句同时为空或者同时不为空
if(p == null && q == null){
return true;
}
//结构相同之后判断值是否一样
if(p.val != q.val){
return false;
}
//递归 跟的左子树是否一样 跟的右子树是否一样
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}7.另一颗树的子树
设root共有r个节点，subRoot共有s个节点，该方式下的时间复杂为O（r*s）。
**
* 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 boolean isSameTree(TreeNode p, TreeNode q) {
//先判断两颗树的结构是否相同
if(p !=null && q == null || p == null && q != null){
return false;
}
//上述语句入果没有执行说明两个语句同时为空或者同时不为空
if(p == null && q == null){
return true;
}
//结构相同之后判断值是否一样
if(p.val != q.val){
return false;
}
//递归 跟的左子树是否一样 跟的右子树是否一样
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}8.翻转二叉树
/**
* 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 root;
}
if(root.left == null && root.right == null){
return root;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}9.对称二叉树
/**
* 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 boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
return isSymmetricChildren(root.left,root.right);
}
public boolean isSymmetricChildren(TreeNode leftTree,TreeNode rightTree){
if(leftTree == null && rightTree != null || leftTree != null && rightTree == null){
return false;
}
if(leftTree == null && rightTree == null){
return true;
}
if(leftTree.val != rightTree.val){
return false;
}
return isSymmetricChildren(leftTree.left,rightTree.right) && isSymmetricChildren(leftTree.right,rightTree.left);
}
}
10.平衡二叉树
解法一：时间复杂度为O（n^2 ）
/**
* 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 boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
int leftHight = getHeight(root.left);
int rightHight = getHeight(root.right);
return Math.abs(leftHight-rightHight) < 2 && isBalanced(root.left) && isBalanced(root.right);
}
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return leftHeight > rightHeight
? leftHeight + 1
: rightHeight + 1;
}
}解法二：时间复杂度O（n）
/**
* 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 boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
return getHeight(root) >= 0;
}
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
if(leftHeight < 0){
return -1;
}
int rightHeight = getHeight(root.right);
if( rightHeight >=0 && Math.abs(rightHeight - leftHeight) <= 1 ){
return Math.max(rightHeight,leftHeight)+1;
}else{
return -1;
}
}
}11.而叉搜索树与双向链表
import java.util.*;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode prev = null;
public TreeNode Convert(TreeNode pRootOfTree) {
if ( pRootOfTree == null) {
return null;
}
ConvertChild(pRootOfTree);
TreeNode head = pRootOfTree;
while (head.left != null) {
head = head.left;
}
return head;
}
public void ConvertChild(TreeNode root) {
if (root == null) {
return;
}
ConvertChild(root.left);
//打印
root.left = prev;
if (prev != null) {
prev.right = root;
}
prev = root;
ConvertChild(root.right);
}
}11.二叉树遍历
import java.util.Scanner;
public class Main {
static class TreeNode {
char val;
public TreeNode left;
public TreeNode right;
public TreeNode( char val) {
this.val = val;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine() ) { // 注意 while 处理多个 case
String str = in.nextLine();
TreeNode root = createTree(str);
inorderTree(root);
}
}
public static int i = 0;
public static TreeNode createTree(String str){
TreeNode root = null;
if(str.charAt(i) != '#'){
root = new TreeNode(str.charAt(i));
i++;
root.left = createTree(str);
root.right = createTree(str);
}else{
i++;
}
return root;
}
public static void inorderTree(TreeNode root){
if(root == null){
return;
}
inorderTree(root.left);
System.out.print(root.val+" ");
inorderTree(root.right);
}
}
