递归和二叉树

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

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

  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)
};