递归和二叉树

写了几个程度为简单的二叉树题目,都是和递归有关

二叉树是一种常见的树状数据结构,其中每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树的每个节点包含一个值以及指向其左右子节点的指针。以下是二叉树的一些基本概念:

  1. 根节点(Root):二叉树的顶部节点,没有父节点的节点。
  2. 叶子节点(Leaf):没有子节点的节点称为叶子节点,即左右子节点都为空的节点。
  3. 内部节点(Internal Node):有至少一个子节点的节点称为内部节点。
  4. 子树(Subtree):二叉树中的任意节点和其所有后代节点,形成的结构称为子树。
  5. 深度(Depth):从根节点到某个节点的唯一路径的边数。
  6. 高度(Height):从某个节点到其最远叶子节点的路径的边数,也可以理解为该节点所在子树的深度。

二叉树有多种不同的类型,包括但不限于:

  • 二叉搜索树(Binary Search Tree,BST):一种特殊的二叉树,左子树上的节点值都小于根节点的值,右子树上的节点值都大于根节点的值。

  • 平衡二叉树(Balanced Binary Tree):一种高度平衡的二叉树,保证每个节点的左右子树的高度差不超过1,以确保检索、插入和删除操作的高效性。

  • js返回二叉树的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//  中序遍历:左中右
var inorderTraversal = function (root) {
const arr = []
// 递归
function traverse(root){
if(root==null) return
// 左
traverse(root.left)
// 将根值push进数组
arr.push(root.val)
// 右
traverse(root.right)
}
traverse(root)
return arr
};
  • js计算二叉树的最大深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var maxDepth = function (root) {
// 递归计算左右子树的最大深度,取最大的一个+1
function comDepth(root){
if(root===null){
return 0
}else{
const leftDepth=comDepth(root.left)
const rightDepth=comDepth(root.right)
// Math.max() 是 JavaScript 中的一个内置函数,用于返回一组数中的最大值
return Math.max(leftDepth,rightDepth)+1
}
}
// 记得返回
return comDepth(root)


};
  • js翻转二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var invertTree = function (root) {

// 递归翻转
function reverse(root) {
if (root == null) {
// 注意要返回null
return null
}
const left = reverse(root.left)
const right = reverse(root.right)
root.left = right
root.right = left
return root
}
return reverse(root)
};

if语句里的return语句直接return是因为这个return语句处于一个递归函数内部。在递归函数内部,当满足某个条件时(比如节点为空),递归函数可以直接返回,这意味着递归的结束。

遇到空节点不能结束的行为需要指定return的值

  • js检查二叉树是否轴对称
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var isSymmetric = function (root) {
function isSymmetric(root){
function isMirror(left,right) {
// 两节点为空对称
if (left == null && right == null) {
return true
}
if(left==null||right==null){
return false
}
if(left.val!==right.val){
return false
}
return isMirror(left.left,right.right)&&isMirror(left.right,right.left)
}
return isMirror(root,root)
}
return isSymmetric(root)
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var sortedArrayToBST = function (nums) {
function sortTree(nums) {
if (!nums.length) {
return null
}
let mid = Math.floor(nums.length / 2)
let root = new TreeNode(nums[mid])
// 递归构建左右子树
root.left = sortTree(nums.slice(0, mid))//不包含最后一个
root.right = sortTree(nums.slice(mid + 1))
return root
}
return sortTree(nums)
};