题目出自LeetCodehttps://leetcode-cn.com

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
二叉搜索树的中序遍历是一个升序的序列

var isValidBST = function(root) {
    let flag =true
    let max = -Number.MAX_VALUE
    const search = root =>{
        if(root){
            search(root.left)
            if(root.val>max){
                max = root.val
            }else{
                flag = false
            }
            search(root.right)
        }
    }
    search(root)
    return flag
}

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

var lowestCommonAncestor = function(root, p, q) {
    if(root ==null ||root == p ||root ==q) return root
    const left = lowestCommonAncestor(root.left,p,q)
    const right = lowestCommonAncestor(root.right,p,q)
    return left==null?right:right==null?left:root

};

二叉树遍历(递归)

中序遍历

var inorderTraversal = function(root) {
    let arr = []
    if(root == null) return []
    inorder(root,arr)
    return arr
};
var inorder = function(root,arr){
    if(root.left) inorder(root.left,arr)
    arr.push(root.val)
    if(root.right) inorder(root.right,arr)
}

前序遍历

var preorderTraversal = function(root) {
    let arr = []
    if(root == null) return []
    inorder(root,arr)
    return arr
};
var inorder = function(root,arr){
    arr.push(root.val)
    if(root.left) inorder(root.left,arr)
    if(root.right) inorder(root.right,arr)
}

二叉树遍历（非递归）

中序

var inorderTraversal = function(root) {
    if(root == null) return []
    let arr = []
    let stack = []
    while(root!==null || stack.length!==0){
        while(root!==null){
        stack.push(root)
        root = root.left
        }
        root = stack.pop()
        arr.push(root.val)
        root = root.right
    }
    return arr
};

前序

var preorderTraversal = function(root) {
    if(root ==null) return []
    var stack = []
    var arr = []
    while(root !== null ||stack.length!==0){
        while(root!==null){
            stack.push(root)
            arr.push(root.val)
            root = root.left
        }
        root = stack.pop()
        root = root.right
    }
    return arr 
};

二叉树的层序遍历

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]

var levelOrder = function(root) {
    var res = []
    var level = 0
    function BFS(node,level){
        if(node){
            if(!res[level]){
                res[level] = []
            }
            res[level].push(node.val)
            level+=1
            BFS(node.left,level)
            BFS(node.right,level)
        }
    }
    BFS(root,level)
    return res
};

二叉树的最大深度

var maxDepth = function(root) {
    if(!root) return 0
    return 1+Math.max(maxDepth(root.left),maxDepth(root.right))
};

二叉树的最小深度

var minDepth = function(root) {
    if(!root) return 0
    if(root.left==null && root.right !== null){
        return 1+Math.min(minDepth(root.right))
    }
    if(root.left!==null && root.right===null){
        return 1+Math.min(minDepth(root.left))
    }
    return 1+Math.min(minDepth(root.left),minDepth(root.right))
};

括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]