首页 重启DAY7 二叉树与递归PLUS
文章
取消

重启DAY7 二叉树与递归PLUS

发表于 2026/04/25 更新于 2026/04/27
作者 Tonite14
11 分钟阅读

跟着灵茶山艾府大佬学习算法思路的day7，目标是在一个月内掌握hot100

b站链接如下：

如何灵活运用递归？【基础算法精讲 10】

相同的树 题目描述：

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

img

1
2

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

img

1
2

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

img

1
2

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

  • 两棵树上的节点数目都在范围 [0, 100] 内
  • -104 <= Node.val <= 104

思路：

依旧也是从左右子树入手，如果左右子树都是递归相同，就能说明两棵二叉树相同。然后考虑边界条件，这里的边界条件显然是当子树为空时，此时左右子树当然也要保持同时为空才能说明相同。

对于空节点的边界条件，不需要考虑值的问题，而对于普通节点，就要添加一个值相同的条件。

代码：

1
2
3
4
5
6

var isSameTree = function(p, q) {
    if (p === null || q === null) {
        return p === q; // 必须都是 null
    }
    return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

总结：

还是经典的递归思路。

对称二叉树 题目描述：

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

示例 1：

img

1
2

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

img

1
2

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

  • 树中节点数目在范围 [1, 1000] 内
  • -100 <= Node.val <= 100

思路：

和上一题类似，不过是由每两棵树每个对应节点的左右节点都相同变成了一棵树里的每个对应节点的左右节点的对称相同。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

var isSymmetric = function(root) {
    return isMirror(root.left, root.right);
};

function isMirror(left, right) {
    // 两个节点都为空
    if (!left && !right) return true;
    
    // 一个为空，一个不为空
    if (!left || !right) return false;
    
    // 节点值不相等
    if (left.val !== right.val) return false;
    
    // 递归比较：左子树的左和右子树的右，左子树的右和右子树的左
    return isMirror(left.left, right.right) && isMirror(left.right, right.left);
}

灵神的解法，从上一题修改而来：

1
2
3
4
5
6
7
8
9
10

var isSymmetric = function(root) {
    // 100. 相同的树（改成镜像判断）
    function isSameTree(p, q) {
        if (p === null || q === null) {
            return p === q;
        }
        return p.val === q.val && isSameTree(p.left, q.right) && isSameTree(p.right, q.left);
    }
    return isSameTree(root.left, root.right);
};

总结：

还有一个和上一题不一样的地方是两种解法都用了两个函数，这是因为根节点本身没有对称对象能够比较，它的作用是用于拆分递归入口，它的左右子树才能进行递归比较。递归函数的参数也必须是两个，一左一右，而isSymmetric只有一个参数root，参数数量也是不匹配的。

平衡二叉树 题目描述：

给定一个二叉树，判断它是否是 平衡二叉树

示例 1：

img

1
2

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

img

1
2

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

1
2

输入：root = []
输出：true

思路：

这道题的递归过程和二叉树的最大深度是类似的，也是判断高度，但是这里是判断左右子树的高度差的绝对值是否大于1。题目要求的是返回输入的树是否为平衡二叉树，所以在左右子树不平衡时我们可以考虑返回-1，然后将-1逐层向上传递，最终返回false。剩下的结果自然就是平衡。

代码：

灵神的自底向上的做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function getHeight(node) {
    if (node === null) {
        return 0;
    }
    const leftH = getHeight(node.left);
    if (leftH === -1) {
        return -1; // 提前退出，不再递归
    }
    const rightH = getHeight(node.right);
    if (rightH === -1 || Math.abs(leftH - rightH) > 1) {
        return -1;
    }
    return Math.max(leftH, rightH) + 1;
}

var isBalanced = function(root) {
    return getHeight(root) !== -1;
};

总结：

时间复杂度和空间复杂度都是o(n)。还有一种做法是o(n^2)的，这种做法通过自底向上返回-1，可以节省很多计算。

代码看懂了，但是自己来做还是有点卡涩，后面多做做递归吧。

o(n^2)方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function isBalanced(root) {
    if (!root) return true;
    
    // 每次调用getHeight都会遍历整个子树
    const leftHeight = getHeight(root.left);  // O(n)
    const rightHeight = getHeight(root.right); // O(n)
    
    // 递归调用isBalanced，每个节点都会被多次计算高度
    return Math.abs(leftHeight - rightHeight) <= 1 
           && isBalanced(root.left)  // 再次递归遍历左子树
           && isBalanced(root.right); // 再次递归遍历右子树
}

function getHeight(node) {
    if (!node) return 0;
    // 这个函数本身是O(n)的
    return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

对于一棵平衡二叉树： 第1层：1个节点，getHeight需要遍历n个节点 第2层：2个节点，每个getHeight需要遍历n/2个节点 第3层：4个节点，每个getHeight需要遍历n/4个节点 总计算量 ≈ n + 2(n/2) + 4(n/4) + … = n * log₂n

二叉树的右视图 题目描述：

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：

输入：root = [1,2,3,null,5,null,4]

输出：[1,3,4]

解释：

img

示例 2：

输入：root = [1,2,3,4,null,null,null,5]

输出：[1,3,4,5]

解释：

img

示例 3：

输入：root = [1,null,3]

输出：[1,3]

示例 4：

输入：root = []

输出：[]

思路：

需要的是右视图，可以先递归右子树，再递归左子树，由此产生两个问题：第一个是如何记录节点，第二个是如何判断节点是否需要被记录到答案中。

那么可以考虑在递归同时维持一个递归深度，我们已知每一层都会有一个节点需要被记录，每一层对应一个深度值，当递归深度第一次等于来到本层所对应的深度时（递归深度在遍历不同分支时会反复变化），就可以记录下这个深度对应的节点。

这是dfs的解法，还有一种bfs层序遍历的解法，在层序遍历基础上保存遍历时每一层的最后一个节点即可。

代码：

dfs：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

var rightSideView = function(root) {
    const ans = [];
    function dfs(node, depth) {
        if (node === null) {
            return;
        }
        if (depth === ans.length) { // 这个深度首次遇到
            ans.push(node.val);
        }
        dfs(node.right, depth + 1); // 先递归右子树，保证首次遇到的一定是最右边的节点
        dfs(node.left, depth + 1);
    }

    dfs(root, 0);
    return ans;
};

bfs：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

var rightSideView = function(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    // 层序遍历
    while (queue.length) {
        const levelSize = queue.length;
        
        // 处理当前层的所有节点
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            if (i === levelSize - 1) result.push(node.val);
            
            // 将子节点加入队列
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
    }
    
    return result;
};

总结：

自己第一次做是采用层序的做法，在灵神这里又学了dfs的做法，两种做法对比消化一下。

力扣算法
递归 二叉树
本文由作者按照 CC BY 4.0 进行授权
最近更新
文章内容

阅读DAY8 JavaScript高级程序设计 7章上 迭代器与生成器

重启DAY8 二叉树的最近公共祖先