从零开始Leetcode – Day 2
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.
1
2
3
4
5
6
7
8
9
10
11
| var lowestCommonAncestor = function(root, p, q) {
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);
}else{
return root;
}
};
|
Invert Binary Tree
1
2
3
4
5
6
7
8
9
10
11
| var invertTree = function(root) {
if(root === null){
return null;
}
var tempLeft = root.left;
var tempRight = root.right;
root.left = invertTree(tempRight);
root.right = invertTree(tempLeft);
return root;
};
|
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
| var minDepth = function(root) {
if(root === null){
return 0;
}
if(root.left === null){
return minDepth(root.right) + 1;
}
if(root.right === null){
return minDepth(root.left) + 1;
}
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};
|
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.
1
2
3
4
5
6
7
8
9
| var hasPathSum = function(root, sum) {
if( root === null){
return false;
}
if(root.left === null && root.right === null && root.val == sum){
return true;
}
return hasPathSum(root.left , sum - root.val) || hasPathSum(root.right, sum - root.val);
};
|