1. Arrange the coins
Problem: You have n coins in total, and you need to arrange them in a ladder shape. Row K must have exactly k coins.
Given a number n, find the total number of rows that can form a complete ladder row. N is a non-negative integer and is in the range of 32 bit signed integers.
Example 1:
n = 5
The coins can be arranged in the following lines: ¤¤¤¤
Return 2 because the third line is incomplete. Example 2:
n = 8
The coins can be arranged in the following lines: ¤¤¤¤¤
Idea 1:
Arithmetic sequence general term formula, summation formula
Given the sum of the arithmetic sequence Sn, a1=1, d=1, find n
public int arrangeCoins(int n) {
return (int) (-1 + Math.sqrt(1 + 8 * (long) n)) / 2;
}
Copy the code2.[Pow(x, n)]
Title: Implement POw (x, n), i.e., calculate x to the NTH power (i.e., xn).
Example 1:
Input: x = 2.00000, n = 10 Output: 1024.00000 Example 2:
Input: x = 2.10000, n = 3 Output: 9.26100 Example 3:
Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25
public static double myPow(double x, int n) {
if(n==0) return 1;
if(n==1) return x;
if(n==-1) return 1/x;
double half=myPow(x,n/2);
double rest=myPow(x,n%2);
return half*half*rest;
}
Copy the code3. The maximum depth of the binary tree
Given a binary tree, find its maximum depth.
The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.
Note: A leaf node is a node with no child nodes.
Example: given a binary tree [3,9,20,null,null,15,7],
3
Copy the code/ 9 20/15 7 returns its maximum depth of 3.
public static int maxDepth(TreeNode root) { if(root == null){ return 0; } int left = maxDepth(root.left); int right = maxDepth(root.right); return (left > right? left:right)+1; }Copy the code4. Symmetric binary trees
Title: please implement a function to determine whether a binary tree is symmetric. Note that if a binary tree is the same as the mirror image of the binary tree, it is defined as symmetric.
First of all, the root node and its left and right subtrees, the left subtree of the left subtree and the right subtree of the right subtree are the same, the right subtree of the left subtree and the left subtree of the right subtree are the same, the use of recursion, and non-recursion can also be, the use of stack or queue access at all levels of the root node.
Method one:
boolean isSymmetrical(TreeNode pRoot)
{
if(pRoot==null) return true;
return isSymmetrical(pRoot.left,pRoot.right);
}
private boolean isSymmetrical(TreeNode left, TreeNode right) {
if(left==null&&right==null) return true;
if(left==null||right==null) return false;
if(left.data==right.data)
return isSymmetrical(left.left, right.right)&&isSymmetrical(left.right, right.left);
return false;
}
Copy the code5. Minimum distance of binary search tree
Given the root node of a binary search tree, return the minimum value of the difference between any two nodes in the tree.
Example:
Input: root = [4,2,6,1,3,null,null] output: 1 explanation: note that root is a TreeNode object, not an array.
The given tree [4,2,6,1,3,null,null] can be represented as the following:
4
/ \
2 6
/ \
1 3
Copy the codeThe smallest difference is 1, which is the difference between node 1 and node 2, and the difference between node 3 and node 2.
Definition: Binary Search Tree (Binary Search Tree), (also: Binary Search Tree, Binary sort Tree) it is either an empty Tree, or a Binary Tree with the following properties: if its left subtree is not empty, all nodes in the left subtree are less than the value of its root; If its right subtree is not empty, then the value of all nodes in the right subtree is greater than the value of its root; Its left and right subtrees are also binary sorting trees.
class Solution {
Integer prev = null, ans = Integer.MAX_VALUE;
public int minDiffInBST(TreeNode root) {
test(root);
return ans;
}
public void test(TreeNode treeNode) {
if (treeNode == null) {
return;
}
test(treeNode.left);
if (prev != null) {
ans = Math.min(ans, treeNode.val - prev);
}
prev = treeNode.val;
test(treeNode.right);
}
}
Copy the code6. Print all the paths of the binary tree
Given a binary tree, return all paths from the root node to the leaf node.
Algorithm analysis:
- Suppose the starting node is 1; First, the right child node of node 1 is searched for 2, and then node 1 is set to the searched state. Check whether the two nodes are in the searched state. If the two nodes are not in the searched state, set the two nodes to the searched state. The right adjacent node is searched and judged first each time.
- As shown in the figure, if two nodes have been searched, the right child node is found to be
null;Therefore, the recursion is to search for the left child node 5 on the first node 2, and continue the search to determine that there is no left or right child node on the fifth node, so the recursion returns to the first node; - At this time, the left adjacent node 3 of the search and judgment node 1 is not in the searched state, so the search and judgment operation of the right and then left adjacent nodes is continued.
- Until the last node 3, there are no left or right child nodes, so recursion to the first node 1; End of judgment, end of search.
public void sreachPaths(TreeNode root, List<String> paths, String path) { if(root ! = null) { path += Integer.toString(root.data); if(root.left == null && root.right == null) { paths.add(path); }else { path += "->"; sreachPaths(root.left, paths, path); sreachPaths(root.right, paths, path); }}}Copy the code7. Range sum of binary search tree
Given the root of a binary search tree, return the sum of the values of all nodes between L and R inclusive.
Binary search trees are guaranteed to have unique values.
Example 1:
Input: root = [10,5,15,3,7,null,18], L = 7, R = 15 output: 32
Example 2: input: root = [10,5,15,3,7,13,18,1, null, 6], L = 6, R = 10 output: 23
Tip:
The maximum number of nodes in the tree is 10,000. The final answer is guaranteed to be less than 2^31.
Antithesis thought
The condition gives you the root, and you go from top to bottom. We can use recursion to solve for it. The repeated condition is the left and right subtree of the node, and the ending condition is whether the left and right subtree values are in the range L and R, and returns the sum of the values of the node within the range
public int rangeSumBST(TreeNode root, int L, int R) {
if (root == null) {
return 0;
}
if (root.data < L) {
return rangeSumBST(root.right, L, R);
}
if (root.data > R) {
return rangeSumBST(root.left, L, R);
}
return root.data + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);
}
Copy the code8. The most recent common ancestor of a binary tree
Given a binary tree, find the nearest common ancestor of the two specified nodes in the tree.
The definition of recent public ancestor in Baidu Encyclopedia is: “For two nodes P and Q of the root tree T, the recent public ancestor is expressed as a node X, where x is the ancestor of P and Q and the depth of X is as large as possible (a node can also be its own ancestor).
For example, a given binary tree as follows: root = [3,5,1,6,2,0,8, null, null, 7, 4]
Example 1: input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, output q = 1:3: node 5 and 1 recent common ancestor node 3.
Example 2: input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, q = 4 output: 5: node 5 nodes and four recent common ancestor is 5. Because by definition the most recent common ancestor node can be the node itself.
Note: All nodes have unique values. P and Q are different nodes and exist in a given binary tree.
Ideas:
-
1. Check whether the left and right subtrees contain P or Q respectively. If (two cases: the left subtree contains p, the right subtree contains q/ the left subtree contains Q, and the right subtree contains P),
-
Then the root node is the most recent common ancestor
-
2, if the left subtree contains p and q, then go to root->left to find the most recent common ancestor in the left subtree
-
3, if the right subtree contains p and q, then go to root->right to find the most recent common ancestor in the right subtree
-
Note: It is not possible to return nullptr for both left and right
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || p == root || q == root) { return root; } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left! =null && right! =null) { return root; } return left == null ? right : left; }Copy the code
Idea 2 (non-recursive) :
public TreeNode lowestCommonAncestorII(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == root || q == root) {
return root;
}
List<TreeNode> pPath = findPath(root, p);
List<TreeNode> qPath = findPath(root, q);
TreeNode common = null;
for (int i=0, j=0; i<pPath.size() && j<qPath.size(); i++,j++) {
if (pPath.get(i) == qPath.get(j)) {
common = pPath.get(i);
}
}
return common;
}
private List<TreeNode> findPath(TreeNode root, TreeNode node) {
List<TreeNode> path = new ArrayList<>();
dfs(root, node, new ArrayList<>(), path);
return path;
}
private void dfs(TreeNode root, TreeNode node, List<TreeNode> tmp, List<TreeNode> path) {
if (root == null) {
return;
}
tmp.add(root);
if (root == node) {
path.addAll(new ArrayList<>(tmp));
}
dfs(root.left, node, tmp, path);
dfs(root.right, node, tmp, path);
tmp.remove(tmp.size()-1);
}
Copy the code9. Dance steps
A frog can jump up one or two steps at a time. Figure out how many ways the frog can jump up an n step (the order is different and the result is different).
Consider using Fibonacci sequences (recursion)
Method one: Use the idea of recursion
public class Solution { public int JumpFloor(int target) { if(target<1) return 0; if(target==1) return 1; if(target==2) return 2; return JumpFloor(target-1)+ JumpFloor(target-2); }}Copy the codeApproach two: Use the idea of iteration
public class Solution { public int JumpFloor(int target) { int f1=1,f2=2; while(--target>0){ f2=f2+f1; f1=f2-f1; } return f1; }}Copy the code