101. Symmetric Tree
递归求解
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null)
return true;
return dfs(root,root);
}
public boolean dfs(TreeNode root1,TreeNode root2){
if(root1==null && root2==null)
return true;
if((root1==null || root2==null) || root1.val != root2.val)
return false;
return dfs(root1.left,root2.right) && dfs(root1.right,root2.left);
}
}
102. Binary Tree Level Order Traversal
使用java里的队列
/**
* 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) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root==null)
return res;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
Queue<TreeNode> row = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> onerow = new ArrayList<Integer>();
while(!queue.isEmpty()){
row.offer(queue.poll());
}
while(!row.isEmpty()){
TreeNode t = row.poll();
System.out.println(t.val);
if(t.left!=null)
queue.offer(t.left);
if(t.right!=null)
queue.offer(t.right);
onerow.add(t.val);
}
res.add(onerow);
}
return res;
}
}
103. Binary Tree Zigzag Level Order Traversal
同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>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
boolean order = true;
int size = 1;
while(!q.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
for(int i = 0; i < size; ++i) {
TreeNode n = q.poll();
if(order) {
tmp.add(n.val);
} else {
tmp.add(0, n.val);
}
if(n.left != null) q.add(n.left);
if(n.right != null) q.add(n.right);
}
res.add(tmp);
size = q.size();
order = order ? false : true;
}
return res;
}
}
104. Maximum Depth of Binary Tree
递归求解。
/**
* 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. Construct Binary Tree from Preorder and Inorder Traversal
通过前序遍历和中序遍历来还原二叉树，前序遍历的第一个节点是根节点，然后在中序遍历中根节点左侧的即为根节点左子树的节点集合，右侧的即为根节点右侧的节点集合，因此可以递归求解。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper(0, 0, inorder.length - 1, preorder, inorder);
}
public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int inIndex = 0; // Index of current root in inorder
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root.val) {
inIndex = I;
}
}
root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
return root;
}
}
106. Construct Binary Tree from Inorder and Postorder Traversal
通过后序遍历和中序遍历来还原二叉树，后序遍历的最后一个节点是根节点，然后在中序遍历中根节点左侧的即为根节点左子树的节点集合，右侧的即为根节点右侧的节点集合，因此可以递归求解。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return helper(postorder.length-1, 0, inorder.length - 1, inorder, postorder);
}
public TreeNode helper(int postStart, int inStart, int inEnd, int[] inorder, int[] postorder) {
if (postStart < 0 || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(postorder[postStart]);
int inIndex = 0; // Index of current root in inorder
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root.val) {
inIndex = I;
}
}
root.left = helper(postStart-inEnd+inIndex-1, inStart, inIndex - 1, inorder, postorder);
root.right = helper(postStart-1, inIndex + 1, inEnd, inorder, postorder);
return root;
}
}
107. Binary Tree Level Order Traversal 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) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
if(root == null) return wrapList;
queue.offer(root);
while(!queue.isEmpty()){
int levelNum = queue.size();
List<Integer> subList = new LinkedList<Integer>();
for(int i=0; i<levelNum; i++) {
if(queue.peek().left != null) queue.offer(queue.peek().left);
if(queue.peek().right != null) queue.offer(queue.peek().right);
subList.add(queue.poll().val);
}
wrapList.add(0, subList);
}
return wrapList;
}
}
108. Convert Sorted Array to Binary Search Tree
每次使用数组中的中间的数作为根节点进行递归求解即可。
/**
* 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) {
if(nums==null || nums.length==0)
return null;
return helper(nums,0,nums.length-1);
}
public TreeNode helper(int[] nums,int left,int right){
if(left > right)
return null;
int mid = (right - left ) /2 + left;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums,left,mid-1);
root.right = helper(nums,mid+1,right);
return root;
}
}
109. Convert Sorted List to Binary Search Tree
核心还是找到链表中的中间节点，那么这里使用快慢指针的思路，快指针一次走两步，慢指针一次只走一步，那么快指针走到头的时候，慢指针所在的位置就是中间节点的位置。
/**
* 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 toBST(head,null);
}
public TreeNode toBST(ListNode head,ListNode tail){
if(head == tail) return null;
ListNode fast = head;
ListNode slow = head;
while(fast!=tail && fast.next!=tail){
fast = fast.next.next;
slow = slow.next;
}
TreeNode root = new TreeNode(slow.val);
root.left = toBST(head,slow);
root.right = toBST(slow.next,tail);
return root;
}
}
110. Balanced Binary Tree
平衡二叉树，左右子树的高度差不超过1，因此核心是高度的计算，这里使用了一个小技巧，即遇到高度差大于-1，就返回-1，而且只要遇到-1，-1会不断往前返回，直到返回第一次调用的地方。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root)!=-1;
}
public int height(TreeNode root){
if(root==null)
return 0;
int left = height(root.left);
if(left == -1)
return -1;
int right = height(root.right);
if(right == -1)
return - 1;
if(left-right > 1 || right - left > 1)
return -1;
return Math.max(left,right) + 1;
}
}
