# 初级算法 树
# 二叉树的最大深度
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
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