算法 : 二叉树 - Eureka的博客

902 字

5 分钟

算法 : 二叉树

2026-05-07

2026-05-26

链表、二叉树与回溯

算法

/

链表、二叉树与回溯

一般有三种遍历方式：

先序遍历：见自顶向下 DFS。中序遍历：见二叉搜索树。后序遍历：见自底向上 DFS。带着问题去做下面的题目：

一般来说，DFS 的递归边界是空节点。在什么情况下，要额外把叶子节点作为递归边界?
在什么情况下，DFS 需要有返回值？什么情况下不需要有返回值？
在什么情况下，题目更适合用自顶向下的方法解决？什么情况下更适合用自底向上的方法解决？

遍历二叉树#

自顶向下 DFS（先序遍历）#

在「递」的过程中维护值。

有些题目自顶向下和自底向上都可以做。有些题目也可以用 BFS 做。

自底向上 DFS（后序遍历）#

在「归」的过程中计算

1
class Solution {
2
public:
3
    bool isSameTree(TreeNode* p, TreeNode* q) {
4
        if(p == nullptr || q == nullptr){
5
            return p == q;
6
        }
7

8
        return p->val == q->val && isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
9
    }
10
};

§自底向上 DFS：删点#

1
class Solution {
2
public:
3
    TreeNode* pruneTree(TreeNode* root) {
4
        if (root == nullptr) return nullptr;
5

6
        root->left = pruneTree(root->left);
7
        root->right = pruneTree(root->right);
8

9
        if (root->val == 0 && root->left == nullptr && root->right == nullptr) {
10
            return nullptr;
11
        }
12

13
        return root;
14
    }
15
};

§有递有归#

§二叉树的直径#

§回溯#

§最近公共祖先#

§二叉搜索树#

一般是中序遍历。

搜索树中序遍历的结果是递增的.

98. 验证二叉搜索树

1
class Solution {
2
    long long pre = LLONG_MIN;
3
public:
4
    bool isValidBST(TreeNode* root) {
5
        if (root == nullptr) {
6
            return true;
7
        }
8
        if (!isValidBST(root->left)) { // 左
9
            return false;
10
        }
11
        if (root->val <= pre) { // 中
12
            return false;
13
        }
14
        pre = root->val;
15
        return isValidBST(root->right); // 右
16
    }
17
};