目录
1.链表回文结构
2.相交链表
3.环形链表
4.返回相遇点的值
5.二叉树的前序遍历
6.相同的树力扣
7.另一颗树的子树
8.翻转二叉树
9.对称二叉树
10.平衡二叉树
11.而叉搜索树与双向链表
11.二叉树遍历
编辑
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 hereListNode 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 处理多个 caseString 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);}
}
