初级算法 树

二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

var maxDepth = function(root) {
    if(root == null) return 0
    let max = 0
    function traverse(node,depth){
        depth +=1
        if(depth > max) max = depth
        node.left && traverse(node.left, depth)
        node.right && traverse(node.right, depth)
    }
    traverse(root,0)
    return max
};

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

var isValidBST = function(root) {
    let valid = true
    let list = []
    function traverse(node){
    node.left && traverse(node.left)
    list.push(node.val)
    node.right && traverse(node.right)
    }
    traverse(root)
    for(let i = 0; i < list.length -1 ; i++){
        let prev = list[i]
        let next = list[i+1]
        if(prev >= next) valid = false
    }
    return valid
};

对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

var isSymmetric = function(root) {
    function traverse(left, right){
        if(left == null && right == null) return true
        if(left == null || right == null) return false
        if(left.val != right.val) return false
        return traverse(left.left,right.right) && traverse(left.right, right.left)
    }
    return traverse(root.left, root.right)
};

二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

var levelOrder = function(root) {
    if(root == null) return []
    let queue = []
    queue.push(root)
    let result = []
    while(queue.length){
        let list = []
        while(queue.length){
            let node = queue.shift()
            list.push(node)
        }
        let arr = list.map(item=> item.val)
        result.push(arr)
        while(list.length){
            let node = list.shift()
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
        }
    }
    return result
};

将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

TIP

TODO