发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    	if(root == null || p == null || q == null) {
        	return null;
    	}
      	if(root.val == p.val || root.val == q.val) {
        	return root;
      	}
        if((root.val < p.val && root.val > q.val) || (root.val < q.val && root.val > p.val)) {
        	return root;
        }
        if(root.val < p.val && root.val < q.val) {
         	return lowestCommonAncestor(root.right, p, q);
        }
        return lowestCommonAncestor(root.left, p, q);
    }
}

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/combination-sum-iv/

　　给你一个数组和一个target值，求数组中的组合的和等于target，121和112，211视为不同的。

题目分析

　　动态规划不仅可以解决最优值问题，可以解决很多计数类问题。想解决目标值为target的问题要借助于目标值比target小的子问题。结果数组为dp，所求的为dp[target]。dp[i] = dp[i] + dp[i - x]，x为nums数组中的值，意思是想解决dp[i]，如果dp[i-x]已经解决了，再把x值加入这一组合中就成为一个解了。注意下，dp［0］为1，因为这是起始情况，比如数组只有一个元素1，target也为1，dp[0]显然得为1的情况下，结果dp[1]才能为1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = 1; i <= target; i++) {
            for(int x : nums) {
                if(i >= x) {
                    dp[i] += dp[i-x];
                }
            }
        }
        return dp[target];
    }
}

　　时间复杂度O(target * num.length)

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/validate-binary-search-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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private List<Integer> list = new ArrayList<Integer>();
    
    private void inOrder(TreeNode root) {
        if(root == null) {
            return ;
        }
        inOrder(root.left);
        list.add(root.val);
        inOrder(root.right);
    }
    
    public boolean isValidBST(TreeNode root) {
        if(root == null) {
            return true;
        }
        inOrder(root);
        int pre = list.get(0);
        int size = list.size();
        for(int i = 1; i < size; i++) {
            if(list.get(i) <= pre) {
                return false;
            }
            pre = list.get(i);
        }
        return true;
    }
}

　　时间复杂度O(n)，n为树的节点个数