【前端面试】二叉树递归模板和题解

发布于:2024-06-25 ⋅ 阅读:(140) ⋅ 点赞:(0)


知乎拿的图

递归题目的通用步骤

  1. 明确递归函数的功能:确定递归函数的输入参数和返回值,明确函数的功能。
  2. 基准情况(递归终止条件):设立一个或多个递归终止条件,确保递归能够结束。
  3. 递归步骤:将问题分解为更小的子问题,通过递归调用自身解决这些子问题。
  4. 合并结果:将子问题的解合并成原问题的解。

递归模板总结

1. 树的遍历(DFS)

前序遍历(根 -> 左 -> 右)

function preorderTraversal(root) {
    let result = [];
    function traverse(node) {
        if (node !== null) {
            result.push(node.val);  // 访问根节点
            traverse(node.left);    // 递归遍历左子树
            traverse(node.right);   // 递归遍历右子树
        }
    }
    traverse(root);
    return result;
}

中序遍历(左 -> 根 -> 右)

function inorderTraversal(root) {
    let result = [];
    function traverse(node) {
        if (node !== null) {
            traverse(node.left);    // 递归遍历左子树
            result.push(node.val);  // 访问根节点
            traverse(node.right);   // 递归遍历右子树
        }
    }
    traverse(root);
    return result;
}

后序遍历(左 -> 右 -> 根)

function postorderTraversal(root) {
    let result = [];
    function traverse(node) {
        if (node !== null) {
            traverse(node.left);    // 递归遍历左子树
            traverse(node.right);   // 递归遍历右子树
            result.push(node.val);  // 访问根节点
        }
    }
    traverse(root);
    return result;
}
2. 二叉树的最大深度
function maxDepth(root) {
    if (root === null) {
        return 0;
    }
    let leftDepth = maxDepth(root.left);
    let rightDepth = maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
}
3. 二叉树的最近公共祖先
function lowestCommonAncestor(root, p, q) {
    if (root === null || root === p || root === q) {
        return root;
    }
    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q);
    if (left !== null && right !== null) {
        return root;
    }
    return left !== null ? left : right;
}

递归题目的记忆技巧

  1. 确定递归函数的功能:明确函数的输入和输出,理解函数的目标。
  2. 设立基准情况:找到递归终止的条件,确保递归能够正确结束。
  3. 分解问题:将问题分解为更小的子问题,并通过递归调用解决。
  4. 合并结果:将子问题的解合并成原问题的解。

网站公告

今日签到

点亮在社区的每一天
去签到