二叉树

Leetcode

104. 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.

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
3
/ \
9 20
/ \
15 7

return its depth = 3.

1
2
3
4
5
6
7
8
9
10
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
//+1是当前的节点
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}

111. 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.

解题思路:

与上一题不同之处在于:找最小距离要注意,可能存在左右子树为空的情况,此时值就为0,但显然值是不为0的(只有当二叉树为空才为0),所以,在这里注意一下即可!

1
2
3
4
5
6
7
8
9
10
class Solution {
public int minDepth(TreeNode root) {
if(root == null){
return 0;
}
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left+right+1 : Math.min(left, right) + 1;
}
}

226. Invert Binary Tree

Invert a binary tree.

1
2
3
4
5
4
/ \
2 7
/ \ / \
1 3 6 9

to

1
2
3
4
5
4
/ \
7 2
/ \ / \
9 6 3 1

解题思路:

翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return root;
}
TreeNode temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}
}

100. Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null){
return true;
}
if(p != null && q != null){
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right) && p.val == q.val;
}
return false;
}
}

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
return helper(root.left, root.right);
}
public boolean helper(TreeNode l, TreeNode r){
if(l == null && r == null){
return true;
}
if(l != null && r != null){
return l.val == r.val && helper(l.left, r.right) && helper(l.right, r.left);
}
return false;
}
}

222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int countNodes(TreeNode root) {
if(root == null){
return 0;
}
int lHeight = height(root.left);
int rHeight = height(root.right);
if(lHeight == rHeight){
return (1 << lHeight) + countNodes(root.right);
}
else{
return (1 << rHeight) + countNodes(root.left);
}
}
private int height(TreeNode node){
if(node == null){
return 0;
}
return 1 + height(node.left);
}
}

110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
return helper(root, 0) != -1;
}
int helper(TreeNode node, int height){
if(node == null){
return height;
}
int lHeight = helper(node.left, height + 1);
int rHeight = helper(node.right, height + 1);
if(Math.abs(lHeight - rHeight) > 1){
return -1;
}
return Math.max(lHeight, rHeight);
}
}

112. 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.

Example:

Given the below binary tree and sum = 22

1
2
3
4
5
6
7
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
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null){
return false;
}
if(root.left == null && root.right == null){
return root.val == sum;
}
sum -= root.val;
return hasPathSum(root.left, sum) ||
hasPathSum(root.right, sum);
}
}

404. Sum of Left Leaves

Find the sum of all left leaves in a given binary tree.

Example:

1
2
3
4
5
3
/ \
9 20
/ \
15 7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root == null){
return 0;
}
int res = 0;
if(root.left != null){
if(root.left.left == null && root.left.right == null){
res += root.left.val;
}
else{
res += sumOfLeftLeaves(root.left);
}
}
res += sumOfLeftLeaves(root.right);
return res;
}
}

257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

Example:

1
2
3
4
5
1
/ \
2 3
\
5

All root-to-leaf paths are:

1
["1->2->5", "1->3"]
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
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new LinkedList<String>();
if(root == null){
return res;
}
if(root.left == null && root.right == null){
res.add(String.valueOf(root.val));
return res;
}
List<String> leftS = binaryTreePaths(root.left);
for(int i = 0; i < leftS.size(); ++i){
res.add(String.valueOf(root.val) + "->" + leftS.get(i));
}
List<String> rightS = binaryTreePaths(root.right);
for(int i = 0; i < rightS.size(); ++i){
res.add(String.valueOf(root.val) + "->" + rightS.get(i));
}
return res;
}
}

113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Example:

Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1

return

1
2
3
4
[
[5,4,11,2],
[5,8,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
class Solution {
private List<List<Integer>> list2 = new ArrayList<List<Integer>>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root == null){
return list2;
}
helper(root, sum, new Stack<Integer>());
return list2;
}
private void helper(TreeNode node, int sum, Stack<Integer> stack){
stack.push(node.val);
if(node.left == null && node.right == null){
if(node.val == sum){
list2.add(new ArrayList<Integer>(stack));
}
}
if(node.left != null){
helper(node.left, sum - node.val, stack);
}
if(node.right != null){
helper(node.right, sum - node.val, stack);
}
stack.pop();
}
}

129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Example:

1
2
3
1
/ \
2 3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

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
class Solution {
List<List<Integer>> list2 = new ArrayList<List<Integer>>();
public int sumNumbers(TreeNode root) {
if(root == null){
return 0;
}
helper(root, new Stack<Integer>());
int res = 0;
for(List<Integer> l : list2){
int sum = 0;
int factor = 1;
for(int i = l.size() - 1; i >= 0; --i){
sum += factor * l.get(i);
factor *= 10;
}
res += sum;
}
return res;
}
public void helper(TreeNode root, Stack<Integer> stack){
stack.push(root.val);
if(root.left == null && root.right == null){
list2.add(new ArrayList<Integer>(stack));
}
if(root.left != null){
helper(root.left, stack);
}
if(root.right != null){
helper(root.right, stack);
}
stack.pop();
}
}

437. Path Sum III

ou are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
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
class Solution {
public int pathSum(TreeNode root, int sum) {
if(root == null){
return 0;
}
int res = helper(root, sum);
res += pathSum(root.left, sum);
res += pathSum(root.right, sum);
return res;
}
private int helper(TreeNode node, int remain){
if(node == null){
return 0;
}
int res = 0;
if(node.val == remain){
res = 1;
}
res += (helper(node.left, remain - node.val) + helper(node.right, remain - node.val) );
return res;
}
}

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

Example:

1
2
3
4
5
6
7
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return null;
}
if(root.val < p.val && root.val < q.val){
return lowestCommonAncestor(root.right, p, q);
}
else if(root.val > p.val && root.val > q.val){
return lowestCommonAncestor(root.left, p, q);
}
return root;
}
}

98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Example:

1
2
3
4
2
/ \
1 3
return true
1
2
3
4
1
/ \
2 3
return false
1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isValidBST(TreeNode root) {
return helper(root, null, null);
}
boolean helper(TreeNode root, Integer min, Integer max) {
if (root == null)
return true;
if ((min != null && root.val <= min) || (max != null && root.val >= max))
return false;
return helper(root.left, min, root.val) && helper(root.right, root.val, max);
}

450. Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Note: Time complexity should be O(height of tree).

Example:

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
root = [5,3,6,2,4,null,7]
key = 3
5
/ \
3 6
/ \ \
2 4 7
Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
5
/ \
4 6
/ \
2 7
Another valid answer is [5,2,6,null,4,null,7].
5
/ \
2 6
\ \
4 7

108. Convert Sorted Array to Binary Search Tree

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

Example:

1
2
3
4
5
6
7
8
9
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums == null){
return null;
}
return helper(nums, 0, nums.length-1);
}
private TreeNode helper(int []A, int lo, int hi){
if(lo > hi){
return null;
}
int mid = (lo + hi) / 2;
TreeNode node = new TreeNode(A[mid]);
node.left = helper(A, lo, mid-1);
node.right = helper(A, mid+1, hi);
return node;
}
}

230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:

You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

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
class Solution
{ private static int count = 0;
private static int res = 0;
public int kthSmallest(TreeNode root, int k) {
if(root == null){
return 0;
}
count = k;
helper(root, k);
return res;
}
public void helper(TreeNode node, int k){
if(node.left != null){
helper(node.left, k);
}
if(--count == 0){
res = node.val;
return;
}
if(node.right != null){
helper(node.right, count);
}
}
}

236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

1
2
3
4
5
6
7
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4

Example:

the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

1
2