101. 对称二叉树
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return dfs(root.left, root.right);
}
private boolean dfs(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null || left.val != right.val) {
return false;
}
return dfs(left.right, right.left) && dfs(left.left, right.right);
}
}
// 画出图 判断节点的情况有哪几种102. 二叉树的层序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Deque<TreeNode> deque = new LinkedList();
List<List<Integer>> res = new ArrayList();
if (root != null) {
deque.offer(root);
while (!deque.isEmpty()) {
int len = deque.size();
//添加list 比 get判空，空的时候创建好
List<Integer> list = new ArrayList();
while (len-- != 0) {
TreeNode node = deque.poll();
list.add(node.val);
if (node.left != null) deque.offer(node.left);
if (node.right != null) deque.offer(node.right);
}
res.add(list);
}
}
return res;
}
}103. 二叉树的锯齿形层次遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
Deque<TreeNode> deque = new LinkedList();
List<List<Integer>> res = new ArrayList();
if (root != null) {deque.offer(root);}
int level = 0;
while (!deque.isEmpty()) {
int len = deque.size();
List<Integer> list = new ArrayList();
level++;
while (len-- != 0) {
TreeNode node = deque.poll();
list.add(node.val);
if (node.left != null) {
deque.offer(node.left);
}
if (node.right != null) {
deque.offer(node.right);
}
}
if (level % 2 == 0) {
Collections.reverse(list);
}
res.add(list);
}
return res;
}
}104. 二叉树的最大深度
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}105. 从前序与中序遍历序列构造二叉树
前和中 ，中和后 都可以构造唯一的二叉树（前提是节点不重复），前和后是不行的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Map<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
TreeNode build(int[] preorder, int[] inorder, int pl, int pr, int il, int ir) {
if (pl > pr) return null;
TreeNode node = new TreeNode(preorder[pl]);
int index = map.get(preorder[pl]);
node.left = build(preorder, inorder, pl + 1, pl + 1 + index - 1 - il, il, index - 1);
node.right = build(preorder, inorder, pl + 1 + index - 1 - il + 1, pr, index + 1, ir);
return node;
}
}106. 从中序与后序遍历序列构造二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Map<Integer,Integer> map;
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
}
TreeNode build(int[] inorder, int[] postorder, int il, int ir, int pl, int pr) {
if(pl > pr) {
return null;
}
TreeNode node = new TreeNode(postorder[pr]);
int k = map.get(postorder[pr]);
node.left = build(inorder, postorder, il, k - 1, pl, pl + k - 1 - il);
node.right = build(inorder, postorder, k + 1, ir, pl + k - 1 - il + 1, pr - 1);
return node;
}
}107 二叉树的层次遍历 II
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList();
Deque<TreeNode> deque = new LinkedList();
if (root != null) {
deque.offer(root);
}
while (! deque.isEmpty()) {
int len = deque.size();
List<Integer> list = new ArrayList();
while (len-- != 0) {
TreeNode node = deque.poll();
list.add(node.val);
if (node.left != null) deque.offer(node.left);
if (node.right != null) deque.offer(node.right);
}
res.add(list);
}
Collections.reverse(res);
return res;
}
}108. 将有序数组转换为二叉搜索树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0 , nums.length - 1);
}
private TreeNode build(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = (left + right) >> 1;
TreeNode node = new TreeNode(nums[mid]);
node.left = build(nums, left, mid - 1);
node.right = build(nums, mid + 1, right);
return node;
}
}109. 有序链表转换二叉搜索树
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null) {
return null;
}
return build(head,null);
}
TreeNode build(ListNode start, ListNode end) {
if (start == null || start == end) {
return null;
}
ListNode fast = start;
ListNode slow = start;
while (fast.next != end && fast.next.next != end) {
fast = fast.next.next;
slow = slow.next;
}
TreeNode node = new TreeNode(slow.val);
node.right = build(slow.next, end);
node.left = build(start, slow);
return node;
}
}110. 平衡二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
boolean res = true;
public boolean isBalanced(TreeNode root) {
dfs(root);
return res;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
int left = dfs(node.left);
int right = dfs(node.right);
if (Math.abs(left - right) > 1) {
res = false;
}
return Math.max(left, right) + 1;
}
}
京公网安备 11010502036488号