发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 30 Binary Tree Zigzag Level Order Traversal/

访问原文「CODE 30. Binary Tree Zigzag Level Order Traversal」

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},

  3
 / \
9  20
  /  \
 15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

confused what "{1,#,2,3}" means? >
read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:

  1
 / \
2   3
   /
  4
   \
    5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == root) {
		return new ArrayList<ArrayList<Integer>>();
	}
	ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
	Queue<TreeNode> queue = new LinkedList<TreeNode>();
	ArrayList<Integer> layerVals = new ArrayList<Integer>();
	queue.offer(root);
	int layerNumber = 1;
	int layer = 1;
	while (!queue.isEmpty()) {
		TreeNode node = queue.poll();
		layerVals.add(node.val);
		layerNumber--;
		if (null != node.left) {
			queue.offer(node.left);
		}
		if (null != node.right) {
			queue.offer(node.right);
		}
		if (layerNumber == 0) {
			layerNumber = queue.size();
			ArrayList<Integer> layerValsCpy = new ArrayList<Integer>();
			if (layer % 2 == 0) {
				for (int i = layerVals.size() - 1; i >= 0; i--) {
					layerValsCpy.add(layerVals.get(i));
				}
			} else {
				layerValsCpy.addAll(layerVals);
			}
			results.add(layerValsCpy);
			layerVals.clear();
			layer++;
		}
	}
	return results;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 29 Maximum Depth of Binary Tree/

访问原文「CODE 29. Maximum Depth of Binary Tree」

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int maxDepth(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == root) {
		return 0;
	}
	Queue<TreeNode> queue = new LinkedList<TreeNode>();
	queue.offer(root);
	int layer = 1;
	int layerNumbers = 1;
	while (!queue.isEmpty()) {
		TreeNode node = queue.poll();
		layerNumbers--;
		if (null != node.left) {
			queue.offer(node.left);
		}
		if (null != node.right) {
			queue.offer(node.right);
		}
		if (layerNumbers == 0 && !queue.isEmpty()) {
			layerNumbers = queue.size();
			layer++;
		}
	}
	return layer;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 28 Construct Binary Tree from Preorder and Inorder Traversal/

访问原文「CODE 28. Construct Binary Tree from Preorder and Inorder Traversal」

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public TreeNode buildTree(int[] preorder, int[] inorder) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == inorder || null == preorder || inorder.length <= 0
			|| preorder.length <= 0) {
		return null;
	}
	return dfs(inorder, preorder, 0, inorder.length - 1, 0,
			preorder.length - 1);
}
TreeNode dfs(int[] inorder, int[] preorder, int inorderStart,
		int inorderEnd, int preorderStart, int preorderEnd) {
	TreeNode node = new TreeNode(preorder[preorderStart]);
	int nodeIndexInInorder = findElement(inorder, preorder[preorderStart]);
	int leftLength = nodeIndexInInorder - inorderStart;
	int rightLength = inorderEnd - nodeIndexInInorder;
	if (leftLength > 0) {
		TreeNode left = dfs(inorder, preorder, inorderStart,
				nodeIndexInInorder - 1, preorderStart + 1, preorderStart
						+ leftLength);
		node.left = left;
	}
	if (rightLength > 0) {
		TreeNode right = dfs(inorder, preorder, nodeIndexInInorder + 1,
				inorderEnd, preorderEnd - rightLength + 1, preorderEnd);
		node.right = right;
	}
	return node;
}
int findElement(int[] array, int element) {
	for (int i = 0; i < array.length; i++) {
		if (array[i] == element) {
			return i;
		}
	}
	return -1;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 27 Construct Binary Tree from Inorder and Postorder Traversal/

访问原文「CODE 27. Construct Binary Tree from Inorder and Postorder Traversal」

Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public TreeNode buildTree(int[] inorder, int[] postorder) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == inorder || null == postorder || inorder.length <= 0
			|| postorder.length <= 0) {
		return null;
	}
	return dfs(inorder, postorder, 0, inorder.length - 1, 0,
			postorder.length - 1);
}
TreeNode dfs(int[] inorder, int[] postorder, int inorderStart,
		int inorderEnd, int postorderStart, int postorderEnd) {
	TreeNode node = new TreeNode(postorder[postorderEnd]);
	int nodeIndexInInorder = findElement(inorder, postorder[postorderEnd]);
	int leftLength = nodeIndexInInorder - inorderStart;
	int rightLength = inorderEnd - nodeIndexInInorder;
	if (leftLength > 0) {
		TreeNode left = dfs(inorder, postorder, inorderStart,
				nodeIndexInInorder - 1, postorderStart, postorderEnd
						- rightLength - 1);
		node.left = left;
	}
	if (rightLength > 0) {
		TreeNode right = dfs(inorder, postorder, nodeIndexInInorder + 1,
				inorderEnd, postorderEnd - rightLength, postorderEnd - 1);
		node.right = right;
	}
	return node;
}
int findElement(int[] array, int element) {
	for (int i = 0; i < array.length; i++) {
		if (array[i] == element) {
			return i;
		}
	}
	return -1;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 24 Convert Sorted List to Binary Search Tree/

访问原文「CODE 24. Convert Sorted List to Binary Search Tree」

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public TreeNode sortedListToBST(ListNode head) {
	// Start typing your Java solution below
	// DO NOT write main() function
	return dfs(head);
}
TreeNode dfs(ListNode head) {
	TreeNode node = null;
	if (head != null) {
		ListNode perMidNode = null;
		ListNode midNode = head;
		ListNode lastNode = head;
		while (null != lastNode.next && null != lastNode.next.next) {
			perMidNode = midNode;
			midNode = midNode.next;
			lastNode = lastNode.next.next;
		}
		if (null != perMidNode) {
			perMidNode.next = null;
		}
		node = new TreeNode(midNode.val);
		TreeNode left = dfs(perMidNode == null ? null : head);
		TreeNode right = dfs(midNode.next);
		node.left = left;
		node.right = right;
	}
	return node;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 25 Convert Sorted Array to Binary Search Tree/

访问原文「CODE 25. Convert Sorted Array to Binary Search Tree」

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public TreeNode sortedArrayToBST(int[] num) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (num == null || num.length <= 0) {
		return null;
	}
	return dfs(num, 0, num.length - 1);
}
TreeNode dfs(int[] num, int min, int max) {
	TreeNode node = null;
	if (min <= max) {
		int mid = (max + min) / 2;
		node = new TreeNode(num[mid]);
		TreeNode left = dfs(num, min, mid - 1);
		TreeNode right = dfs(num, mid + 1, max);
		node.left = left;
		node.right = right;
	}
	return node;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/19/2013-09-19-CODE 23 Balanced Binary Tree/

访问原文「CODE 23. Balanced Binary Tree」

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees ofevery node
never differ by more than 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public boolean isBalanced(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == root) {
		return true;
	}
	return checkBalanced(root) != -1;
}
public int checkBalanced(TreeNode root) {
	if (null == root) {
		return 0;
	}
	int left = checkBalanced(root.left);
	int right = checkBalanced(root.right);
	if (left == -1 || right == -1) {
		return -1;
	}
	if (Math.abs(left - right) > 1) {
		return -1;
	} else {
		return Math.max(left, right) + 1;
	}
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/19/2013-09-19-CODE 22 Minimum Depth of Binary Tree/

访问原文「CODE 22. Minimum Depth of Binary Tree」

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int minDepth(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == root) {
		return 0;
	}
	Queue<TreeNode> queue = new LinkedList<TreeNode>();
	queue.offer(root);
	int layer = 1;
	int layerNumbers = 1;
	while (!queue.isEmpty()) {
		TreeNode node = queue.poll();
		layerNumbers--;
		if (null == node.left && null == node.right) {
			break;
		}
		if (null != node.left) {
			queue.offer(node.left);
		}
		if (null != node.right) {
			queue.offer(node.right);
		}
		if (layerNumbers == 0 && !queue.isEmpty()) {
			layerNumbers = queue.size();
			layer++;
		}
	}
	return layer;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/19/2013-09-19-CODE 20 Path Sum II/

访问原文「CODE 20. Path Sum II」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
	if (null == root) {
		return paths;
	}
	dfs(paths, new ArrayList<Integer>(), root, 0, sum);
	return paths;
}
private void dfs(ArrayList<ArrayList<Integer>> paths,
		ArrayList<Integer> path, TreeNode root, int current, int sum) {
	if (root.left == null && root.right == null) {
		if (current + root.val == sum) {
			path.add(root.val);
			ArrayList<Integer> pathCopy = new ArrayList<Integer>();
			pathCopy.addAll(path);
			paths.add(pathCopy);
			path.remove(path.size() - 1);
		}
	}
	path.add(root.val);
	current += root.val;
	if (root.left != null) {
		dfs(paths, path, root.left, current, sum);
	}
	if (root.right != null) {
		dfs(paths, path, root.right, current, sum);
	}
	path.remove(path.size() - 1);
}

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
For example:
Given the below binary tree and sum = 22, 5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/18/2013-09-18-CODE 21 Path Sum/

访问原文「」

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22, 5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum
is 22.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public boolean hasPathSum(TreeNode root, int sum) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == root) {
		return false;
	}
	return dfs(root, 0, sum);
}
private boolean dfs(TreeNode root, int current, int sum) {
	if (root.left == null && root.right == null) {
		if (current + root.val == sum) {
			return true;
		} else {
			return false;
		}
	}
	boolean is = false;
	if (root.left != null) {
		is = dfs(root.left, current + root.val, sum);
	}
	if (is) {
		return is;
	}
	if (root.right != null) {
		is = dfs(root.right, current + root.val, sum);
	}
	return is;
}