递归&分治 2016-08-23

[SnackMen]

98. Validate Binary Search Tree 95. Unique Binary Search Trees II

[SnackMen]

/*
*[AC]98. Validate Binary Search Tree
*二叉搜索树的中序遍历刚刚好可以让二叉树排好序
*/
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode preNode=null;
    public boolean isValidBST(TreeNode root) {
        if(root==null)
            return true;

        if(!isValidBST(root.left))
            return false;
        if(preNode!=null && preNode.val>=root.val)
            return false;
        preNode=root;
        return isValidBST(root.right);
    }
}

[dayang]

/**
 * [AC] LeetCode 98 Validate Binary Search Tree
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {

    var stack = [], flag = true,i;

    function midOrder(rt){
        if(rt === null) return;
        midOrder(rt.left);
        stack.push(rt.val);
        midOrder(rt.right);
    }

    midOrder(root);

    for(i = 1; i < stack.length; i++){
        if(stack[i] <= stack[i-1]){
            flag = false;
            break;
        }
    }

    return flag;
}

[dayang]

/**
 * [AC] LeetCode 95 Unique Binary Search Trees II
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {

    function gTree(l, r) {
        if (r < l) return [];
        if (l === r) return [new TreeNode(l)];
        var i, stack = [], lnodes, rnodes, j, k, newNode;
        for (i = l; i <= r; i++) {
            lnodes = gTree(l, i - 1);
            rnodes = gTree(i + 1, r);

            if (lnodes.length === 0) {
                rnodes.forEach(function (node) {
                    newNode = new TreeNode(i);
                    newNode.right = node;
                    stack.push(newNode);
                });
            } else if (rnodes.length === 0) {
                lnodes.forEach(function (node) {
                    newNode = new TreeNode(i);
                    newNode.left = node;
                    stack.push(newNode);
                });
            } else {
                lnodes.forEach(function (lnode) {
                    rnodes.forEach(function (rnode) {
                        newNode = new TreeNode(i);
                        newNode.left = lnode;
                        newNode.right = rnode;
                        stack.push(newNode);
                    })
                })
            }
        }

        return stack;
    }

    return gTree(1, n);
};

[zhaokuohaha]

C# - 98 - 中序遍历

public class Solution
{
    List<int> res = new List<int>();
    public bool IsValidBST(TreeNode root)
    {
        if (root == null) return true;
        inorder(root);
        if (res.Count < 2) return true;
        for(int i=1;  i<res.Count; i++)
        {
            if (res[i] <= res[i - 1])
                return false;
        }
        return true;
    }

    public void inorder(TreeNode root)
    {
        if (root == null) return;
        inorder(root.left);
        res.Add(root.val);
        inorder(root.right);
    }
}