Leetcode Tree

98 验证二叉搜索树

解法一：进行中序遍历：左中右。并将元素按顺序存到数组里，那么如果是二叉搜索树的话，得到的这个数组就是有序的。用递归来做，这样的坏处就是需要创建很多中间数组，在空间上消耗会大一些。

// 92ms 61.07%   41.4mb 6.92%
var inorder = function (root){
	if (!root){
		return []
	}
	return inorder(root.left).concat(root.val).concat(inorder(root.right))
}
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
	let inorderList = inorder(root)
	for (i = 0; i < inorderList.length-1; i++){
		if (inorderList[i] >= inorderList[i+1]){
			return false
		}
	}
	return true
};

解法2：也是中序遍历，但是每次只要比较前一个节点，省去了创建临时数组的那些操作，所以空间上会节省一些。

// 84ms 75.43%  37.2mb 79.87%
var isValidBST = function(root){
	let pre = null
	let helper = function(root){
		if (!root){
			return true
		}
		if (!helper(root.left)){
			return false
		}
		if (pre !== null && pre >= root.val){
			return false
		}
		pre = root.val
		return helper(root.right)
	}
	return helper(root, pre)
}

235 二叉搜索树的最近公共祖先

因为有二叉搜索树这个特点，因此，那么如果根节点比q，p都大，那么答案肯定在左子树上，如果比qp都小，那么肯定就在右子树上，否则，就是qp一个在左变一个在右边，那么此时的根节点就是qp最近的根节点。

// 84ms 96.65%  43.6mb 73.15%
var lowestCommonAncestor = function(root, p, q) {
    if (root.val > p.val && root.val > q.val){
        return lowestCommonAncestor(root.left, p, q)
    }else if(root.val < p.val && root.val < q.val){
        return lowestCommonAncestor(root.right, p, q)
    }
    return root
};

也可以不写成递归的形式，两者逻辑是一样的。时间空间都差不多

var lowestCommonAncestor = function(root, p, q) {
    while (true){
        if (root.val > p.val && root.val > q.val){
            root = root.left
        }else if(root.val < p.val && root.val < q.val){
            root = root.right
        }else{
            return root
        }
    }
};

236. 二叉树的最近公共祖先

// 112ms 24.19%   41.4mb  43.56%
var lowestCommonAncestor = function(root, p, q) {
    if (root === null || root.val === q.val || root.val === p.val){
        return root
    }
    let left = lowestCommonAncestor(root.left, p, q)
    let right = lowestCommonAncestor(root.right, p, q)
    if (left === null){
        return right
    }else if (right === null){
        return left
    }else{
        return root
    }
};

对比235，总之就是那个道理，如果有一个pq分别在root的左右两边，那么root就是要找的。这个解好像效率不高的样子。