2、树相关算法

红色标题为重点递归题目

基本数据结构：

struct TreeNode {
    int val;
    struct TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
} TreeNode;
1
2
3
4
5

1、二叉树的遍历

// 二叉树的先序遍历（递归）
void Pre(TreeNode *root) {
    if (root) {
        printf("%d ", root->val);
        Pre(root->left);
        Pre(root->right);
    }
}

// 二叉树的先序遍历（迭代）
void Pre(TreeNode *root) {
    stack<TreeNode *> stk;
    TreeNode *p = root;
    while (!stk.empty() || p) {
        if (p) {
            printf("%d ", p->val);
            stk.push(p);
            p = p->left;
        } else {
            p = stk.top();
            stk.pop();
            p = p->right;
        }
    }
}

// 二叉树的中序遍历（递归）
void In(TreeNode *root) {
    if (root) {
        In(root->left);
        printf("%d ", root->val);
        In(root->right);
    }
}

// 二叉树的中序遍历（迭代）
void In(TreeNode *root) {
    stack<TreeNode *> stk;
    TreeNode *p = root;
    while (p || !stk.empty()) {
        if (p) {
            stk.push(p);
            p = p->left;
        } else {
            p = stk.top();
            stk.pop();
            printf("%d ", p->val);
            p = p->right;
        }
    }
}

// 二叉树的后序遍历（递归）
void Post(TreeNode *root) {
    if (root) {
        Post(root->left);
        Post(root->right);
        printf("%d ", root->val);
    }
}

// 二叉树的后序遍历（迭代）
void Post(TreeNode *root) {
    stack<TreeNode *> stk;
    TreeNode *p = root, *r = nullptr;
    while (p || !stk.empty()) {
        if (p) {
            stk.push(p);
            p = p->left;
        } else {
            p = stk.top();
            if (p->right && p->right != r) p = p->right;
            else {
                stk.pop();
                printf("%d ", p->val);
                r = p;
                p = nullptr;
            }
        }
    }
}

// 二叉树的层序遍历
void Level(TreeNode *root) {
    queue<TreeNode *> q;
    q.push(root);
    TreeNode *p;
    while (!q.empty()) {
        p = q.front();
        q.pop();
        printf("%d ", p->val);
        if (p->left) q.push(p->left);
        if (p->right) q.push(p->right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

2、求二叉树的高度(递归做法)

LeetCode 104

// 递归
int Height(TreeNode *root) {
    if (!root) return 0;
    int hl = Height(root->left);
    int hr = Height(root->right);
    return (hl > hr ? hl : hr) + 1;
}

// 迭代
int Height(TreeNode *root) {
    TreeNode *queue[110];
    for (int i = 0; i < 110; i++) queue[i] = nullptr;
    int hh = -1, tt = -1;
    queue[++tt] = root;
    TreeNode *p;
    int last = 0, height = 0;
    while (hh < tt) {
        p = queue[++hh];
        if (p->left) queue[++tt] = p->left;
        if (p->right) queue[++tt] = p->right;
        if (last == hh)height++, last = tt;
    }
    return height;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3、求二叉树的最大宽度(重点)

LeetCode 662

注意：下面代码在 LT 上提交会报错，因为测试用例中树的结点个数大于 $INT$ 所能表示范围。但是思路正确，考研足以。

int Width(TreeNode *root) {
    root->val = 0;
    int maxWidth = 0;
    queue<TreeNode *> q;
    q.push(root);
    while (!q.empty()) {
        int s = q.size();
        int first = 0, last = 0;
        for (int i = 0; i < s; i++) {
            TreeNode *p = q.front();
            q.pop();
            if (!i) first = p->val;
            if (i == s - 1) last = p->val;
            if (p->left) p->left->val = p->val * 2 + 1, q.push(p->left);
            if (p->right) p->right->val = p->val * 2 + 2, q.push(p->right);
        }
        maxWidth = maxWidth > (last - first + 1) ? maxWidth : last - first + 1;
    }
    return maxWidth;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4、判断是否为完全二叉树

bool isComplete(TreeNode *root) {
    queue<TreeNode *> q; q.push(root);
    while (!q.empty()) {
        int s = q.size();
        for (int i = 0; i < s; i++) {
            TreeNode *p = q.front(); q.pop();
            if (!p) {
                while (!q.empty()) {
                    if (q.front()) return false;
                    q.pop();
                }
                return true;
            }
            q.push(p->left), q.push(p->right);
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5、判断是否为平衡二叉树(已考过)

Leetcode 110

int height(TreeNode *root) {
    if (!root) return 0;
    int hl = height(root->left);
    int hr = height(root->right);
    if (hl == -1 || hr == -1 || abs(hl - hr) > 1) return -1;
    return (hl > hr ? hl : hr) + 1;
}

bool is_AVL(TreeNode *root) {
    return height(root) >= 0;
}
1
2
3
4
5
6
7
8
9
10
11

6、判断是否为二叉排序树(已考过)

int pre = -2e9;
bool flag = true;

bool is_BST(TreeNode *root) {
    if (root->left && flag) is_BST(root->left);
    if (root->val < pre) flag = false;
    pre = root->val;
    if (root->right && flag) is_BST(root->right);
    return flag;
}
1
2
3
4
5
6
7
8
9
10

7、翻转二叉树/镜像二叉树(重点)

Leetcode 226

// 递归
TreeNode *Translate(TreeNode *root) {
    if (!root) return nullptr;
    TreeNode *left = Translate(root->left);
    TreeNode *right = Translate(root->right);
    root->left = right, root->right = left;
    return root;
}

// 迭代
TreeNode *Translate(TreeNode *root) {
    queue<TreeNode *> q;
    q.push(root);
    TreeNode *p, *r;
    while (!q.empty()) {
        p = q.front(); q.pop();
        r = p->left;
        p->left = p->right;
        p->right = r;
        if (p->left) q.push(p->left);
        if (p->right) q.push(p->right);
    }
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

8、判断两棵二叉树是否相似(重点)

bool is_Same(TreeNode *root1, TreeNode *root2) {
    bool left, right;
    if (!root1 && !root2) return true;
    if (!root1 || !root2) return false;
    left = is_Same(root1->left, root2->left);
    right = is_Same(root1->right, root2->right);
    return left && right;
}
1
2
3
4
5
6
7
8

9、判断二叉树是否对称(重点)

Leetcode 101

// 递归
bool check(TreeNode *p, TreeNode *q) {
    bool left, right;
    if (!p && !q) return true;
    if (!p || !q) return false;
    left = check(p->left, q->right);
    right = check(p->right, q->left);
    return p->val == q->val && left && right;
}

bool is_symmetry(TreeNode *root) {
    return check(root, root);
}

// 迭代
bool is_symmetry(TreeNode *root) {
    TreeNode *u = root, *v = root;
    queue<TreeNode *> q;
    q.push(u); q.push(v);
    while (!q.empty()) {
        u = q.front(); q.pop();
        v = q.front(); q.pop();
        if (!u && !v) continue;
        if ((!u || !v) || (u->val != v->val)) return false;
        q.push(u->left); q.push(v->right);
        q.push(u->right); q.push(v->left);
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

10、删除子树(重点)

void Release(TreeNode *&root) {
    if (!root) return;
    Release(root->left);
    Release(root->right);
    free(root);
}

// 递归
void Del_Node(TreeNode *&root, int x) {
    if (!root) return;
    if (root->val == x) Release(root), root = nullptr;
    if (root) Del_Node(root->left, x), Del_Node(root->right, x);
}

// 迭代
void Del_Node(TreeNode *&root, int x) {
    if (!root) return;
    queue<TreeNode *> q;
    q.push(root);
    TreeNode *p;
    while (!q.empty()) {
        p = q.front();
        q.pop();
        if (p->left) {
            if (p->left->val == x) Release(p->left), p->left = nullptr;
            else q.push(p->left);
        }
        if (p->right) {
            if (p->right->val == x) Release(p->right), p->right = nullptr;
            else q.push(p->right);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

11、查找某个结点的所有祖先结点(重点)

// 利用后序遍历的特点
void find_pre(TreeNode *root, int x) {
    stack<TreeNode *> stk;
    TreeNode *p = root, *r;
    while (!stk.empty() || p) {
        if (p) stk.push(p), p = p->left;
        else {
            p = stk.top();
            if (p->right && p->right != r) p = p->right;
            else {
                stk.pop();
                if (p->val == x) {
                    while (!stk.empty()) printf("%d ", stk.top()->val), stk.pop();
                    return;
                }
                r = p, p = nullptr;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

12、找出两个结点最近的公共祖先(重要)

Leetcode 236

时间复杂度：$O(n)$ ，空间复杂度：$O(n)$
（其中 $n$ 是指二叉树结点个数）

TreeNode *ans;

class Solution {
public:
    bool dfs(TreeNode *root, TreeNode *p, TreeNode *q) {
        if (!root) return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if ((lson && rson) || (root->val == p->val || root->val == q->val) && (lson || rson)) ans = root;
        return lson || rson || (root->val == p->val || root->val == q->val);
    }

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        dfs(root, p, q);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

13、对于满二叉树，根据先序序列求其后序序列(重要)

void get_post(int pre[], int l1, int r1, int post[], int l2, int r2) {
    if (l1 > r1) return;
    post[r2] = pre[l1];
    int half = (r1 - l1) >> 1;
    get_post(pre, l1 + 1, l1 + half, post, l2, l2 + half - 1);
    get_post(pre, l1 + half + 1, r1, post, l2 + half, r2 - 1);
}
1
2
3
4
5
6
7

14、求解二叉树的带权路径长度(重要)

Acwing 3766

// 递归
int wpl(TreeNode *root, int depth) {
    if (!root) return 0;
    if (!root->left && !root->right) return root->val * depth;
    return wpl(root->left, depth + 1) + wpl(root->right, depth + 1);
}

int get_wpl(TreeNode *root) {
    return wpl(root, 0);
}

// 迭代
int get_wpl(TreeNode *root) {
    TreeNode *queue[110];
    for (int i = 0; i < 110; i++) queue[i] = nullptr;
    int hh = -1, tt = -1;
    queue[++tt] = root;
    int wpl = 0, depth = 0, last = 0;
    while (hh < tt) {
        TreeNode *p = queue[++hh];
        if (p->left) queue[++tt] = p->left;
        if (p->right) queue[++tt] = p->right;
        if (!p->left && !p->right) wpl += depth * p->val;
        if (last == hh) last = tt, depth++;
    }
    return wpl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

15、表达式树(重要)

Acwing 3765

void dfs(TreeNode *root) {
    if (!root) return;
    if (!root->left && !root->right) cout << root->val;
    else {
        cout << '(';
        dfs(root->left);
        cout << root->val;
        dfs(root->right);
        cout << ')';
    }
}

void get_formula(TreeNode *root) {
    dfs(root->left), cout << root->val, dfs(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

16、后缀表达式(重要)

Acwing 4274

#include 
#include 

using namespace std;

const int N = 25;

int n;
string v[N];
int l[N], r[N];
bool st[N]; // 记录是否有

void dfs(int u) {
    cout << '(';
    if (l[u] != -1 && r[u] != -1) {
        dfs(l[u]);
        dfs(r[u]);
        cout << v[u];
    } else if (l[u] == -1 && r[u] == -1) cout << v[u];
    else { // 只有有结点（这时候的减号是负号）
        cout << v[u];
        dfs(r[u]);
    }
    cout << ')';
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> l[i] >> r[i];
        if (l[i] != -1) st[l[i]] = true;
        if (r[i] != -1) st[r[i]] = true;
    }
    int root;
    for (int i = 1; i <= n; i++) // 找出根结点
        if (!st[i]) {
            root = i;
            break;
        }
    dfs(root);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

17、根据先序、中序序列重建二叉树(重点)

Acwing 18、Leetcode 105

注意：该算法要求二叉树中元素不重复

int pos[N];
int pre[N], in[N];

TreeNode *build(int a, int b, int x, int y) {
    if (a > b) return nullptr;
    TreeNode *root = new TreeNode(pre[a]);
    int k = pos[root->val];
    root->left = build(a + 1, a + 1 + k - 1 - x, x, k - 1);
    root->right = build(a + 1 + k - 1 - x + 1, b, k + 1, y);
    return root;
}

TreeNode *BuildTreeNode(int _pre[], int _in[], int len) {
    for (int i = 0; i < len; i++)
        pre[i] = _pre[i], in[i] = _in[i], pos[in[i]] = i;
    return build(0, len - 1, 0, len - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

18、最大的树(重点)

LeetCode 654

class Solution {
public:
    TreeNode *constructMaximumBinaryTree(vector<int> &nums) {
        return build(nums, 0, nums.size() - 1);
    }

    TreeNode *build(const vector<int> &nums, int left, int right) {
        if (left > right) return nullptr;
        int top = left;
        for (int i = left + 1; i <= right; i++)
            if (nums[top] < nums[i]) top = i;
        TreeNode *root = new TreeNode(nums[top]);
        root->left = build(nums, left, top - 1);
        root->right = build(nums, top + 1, right);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

19、二叉树的直径(重点)

Leetcode 543

class Solution {
public:
    int ans; // 记录直径上的结点数目

    int dfs(TreeNode *root) {
        if (!root) return 0;
        int l = dfs(root->left);
        int r = dfs(root->right);
        ans = max(ans, l + r + 1);
        return (l > r ? l : r) + 1;
    }

    int diameterOfBinaryTree(TreeNode *root) {
        ans = 1;
        dfs(root);
        return ans - 1; // ans是路径上结点的数目，边数要-1
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

20、网络延时（树的直径）(重点)

Acwing 3215

注：这题题目使用 DFS 时候只能建立有向图，不能建立无向图，否则会空间不够 (栈溢出)

DFS ：

#include 
#include 
#include 
using namespace std;

const int N = 20010;

int n, m;
int h[N], e[N], ne[N], idx;
int ans;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u) { // 返回当前结点的最大深度
    int d1 = 0, d2 = 0; // 当前结点下的最大深度和次大深度
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        int d = dfs(j);
        if (d >= d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }
    ans = max(ans, d1 + d2 + 1);
    return d1 + 1; // +1 表示加上子树的根结点
}

int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 2; i <= n + m; i++) {
        int p; scanf("%d", &p);
        add(p, i);
    }
    dfs(1);
    printf("%d\n", ans - 1);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

两次 BFS：

#include 
#include 
#include 
#include 

using namespace std;

const int N = 2e4 + 10, M = 2 * N;

int n, m;
int h[N], e[M], ne[M], idx;
int dist[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int bfs(int root) {
    queue<int> q;
    q.push(root);
    memset(dist, -1, sizeof dist);
    dist[root] = 0;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] != -1) continue;
            dist[j] = dist[t] + 1;
            q.push(j);
        }
    }
    int res = 1;
    for (int i = 1; i <= n + m; i++)
        if (dist[res] < dist[i])
            res = i;
    return res;
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n + m; i++) {
        int x;
        scanf("%d", &x);
        add(x, i), add(i, x);
    }
    int p = bfs(1);
    int q = bfs(p);
    printf("%d\n", dist[q]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

21、树的重心(重点)

Acwing 846

#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10, M = N * 2;

int n;
int h[N], e[M], ne[M], idx;
bool st[N];
int ans = N;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u) { // 返回以 u 为根的子树结点数目
    st[u] = true;
    int sum = 1, res = 0; // sum 记录子树结点数目; res 删除该结点后所有连通块中节点数目最大值
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (st[j]) continue;
        int s = dfs(j);
        res = max(res, s);
        sum += s;
    }
    res = max(res, n - sum);
    ans = min(ans, res);
    return sum;
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs(1);
    printf("%d\n", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

22、层数最深叶子结点的和(重点)

LeetCode 1302

class Solution {
public:
    int deepestLeavesSum(TreeNode *root) {
        int res = 0;
        queue < TreeNode * > q;
        q.push(root);
        while (!q.empty()) {
            int s = q.size(), cnt = 0;
            while (s--) {
                TreeNode *p = q.front();
                q.pop();
                cnt += p->val;
                if (p->left) q.push(p->left);
                if (p->right) q.push(p->right);
            }
            res = cnt;
        }
        return res;
    }
};

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

23、哈夫曼树(掌握思路)

Acwing 148

#include 
#include 
#include 

using namespace std;

int main() {
    int n; scanf("%d", &n);
    priority_queue<int, vector<int>, greater<int>> heap;
    while (n--) {
        int x; scanf("%d", &x);
        heap.push(x);
    }
    int res = 0;
    while (heap.size() > 1) {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b);
    }
    printf("%d\n", res);
    return 0;
}

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

24、构造二叉排序树(考察过创建BST)

Acwing 3786

#include 
#include 

using namespace std;

const int INF = 1e8;

typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;

    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
} TreeNode;

TreeNode *root = nullptr;

void insert(TreeNode *&root, int x) {
    if (!root) root = new TreeNode(x);
    else if (x < root->val) insert(root->left, x);
    else insert(root->right, x);
}

void remove(TreeNode *&root, int x) {
    if (!root) return;
    if (x < root->val) remove(root->left, x);
    else if (x > root->val) remove(root->right, x);
    else {
        if (!root->left && !root->right) root = nullptr; // 为叶子节点
        else if (!root->left) root = root->right; // 只有右子树
        else if (!root->right) root = root->left; // 只有左子树
        else {
            auto p = root->left; // 找到左子树中右儿子中的最大值，用其值来代替，并删除其节点
            while (p->right) p = p->right;
            root->val = p->val;
            remove(root->left, p->val);
        }
    }
}

int get_pre(TreeNode *root, int x) {
    if (!root) return -INF;
    if (root->val >= x) return get_pre(root->left, x);
    return max(root->val, get_pre(root->right, x));
}

int get_suc(TreeNode *root, int x) {
    if (!root) return INF;
    if (root->val <= x) return get_suc(root->right, x);
    return min(root->val, get_suc(root->left, x));
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) insert(root, x);
        else if (t == 2) remove(root, x);
        else if (t == 3) cout << get_pre(root, x) << endl;
        else cout << get_suc(root, x) << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

25、求根节点到叶子结点数字之和

Leetcode 129

// dfs
class Solution {
public:
    int dfs(TreeNode *root, int preSum) {
        if (!root) return 0;
        int sum = preSum * 10 + root->val;
        if (!root->left && !root->right) return sum;
        return dfs(root->left, sum) + dfs(root->right, sum);
    }

    int sumNumbers(TreeNode *root) {
        return dfs(root, 0);
    }
};

// bfs
class Solution {
public:
    int sumNumbers(TreeNode *root) {
        queue<TreeNode *> q;
        q.push(root);
        int res = 0;
        while (!q.empty()) {
            TreeNode *p = q.front();
            q.pop();
            if (p->left) p->left->val += p->val * 10, q.push(p->left);
            if (p->right) p->right->val += p->val * 10, q.push(p->right);
            if (!p->left && !p->right) res += p->val;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

26、路径总和

Leetcode 112
$BFS$ 思路正确，但是 $Leetcode$ 上无法通过，后面再改。

// dfs
class Solution {
public:
    bool hasPathSum(TreeNode *root, int targetSum) {
        if (!root) return false;
        if (!root->left && !root->right) return targetSum == root->val;
        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
    }
};

// bfs
bool hasPathSum(TreeNode *root, int targetSum) {
    queue<TreeNode *> q;
    q.push(root);
    bool res = false;
    while (!q.empty()) {
        TreeNode *p = q.front();
        q.pop();
        if (p->left) p->left->val += p->val, q.push(p->left);
        if (p->right) p->right->val += p->val, q.push(p->right);
        if (!p->left && !p->right) res = p->val == targetSum;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

27、统计二叉树中结点个数

int treeNum(TreeNode *root) {
    if (!root) return 0;
    return 1 + treeNum(root->left) + treeNum(root->right);
}
1
2
3
4

28、求二叉树根结点到任意结点的路径

// 仅求路径长度
int dist = 0;

bool NodePathDist(TreeNode *root, TreeNode *target) {
    if (!root) return false;
    dist++;
    if (root == target) return true;
    if (NodePathDist(root->left, target)) return true;
    if (NodePathDist(root->right, target)) return true;
    dist--;
    return false;
}

// 找出路径并打印
stack<TreeNode *> path;

bool NodePath(TreeNode *root, TreeNode *target) {
    if (!root) return false;
    path.push(root);
    if (root == target) return true;
    if (NodePath(root->left, target)) return true;
    if (NodePath(root->right, target)) return true;
    path.pop();
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

29、求二叉树任意两个结点之间的最短距离（考过）

算法思路：
假设任意两个结点 $p、q$ 的公共祖先为 $LCA(p,q)$，从根结点到任意结点之间的最短距离为 $dist(root,p)$，那么任意两个结点之间的最短路径为 $$dist(root,p)+dist(root,q)-2\times LCA(p,q)$$

int dist = 0;

bool NodePathDist(TreeNode *root, TreeNode *target) {
    if (!root) return false;
    dist++;
    if (root == target) return true;
    if (NodePathDist(root->left, target)) return true;
    if (NodePathDist(root->right, target)) return true;
    dist--;
    return false;
}

TreeNode *lca;

bool LCA(TreeNode *root, TreeNode *p, TreeNode *q) {
    if (!root) return false;
    bool hl = LCA(root->left, p, q);
    bool hr = LCA(root->right, p, q);
    if ((hl && hr) || (root->val == p->val || root->val == q->val) && (hl || hr)) lca = root;
    return hl || hr || (root->val == p->val || root->val == q->val);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

30、二叉树的右视图

Leetcode 199

// dfs 基于先序遍历
class Solution {
public:
    vector<int> res;

    void dfs(TreeNode *root, int depth) {
        if (!root) return;
        if (depth == res.size()) res.push_back(root->val);
        depth++;
        dfs(root->right, depth);
        dfs(root->left, depth);
    }

    vector<int> rightSideView(TreeNode *root) {
        dfs(root, 0);
        return res;
    }
};

//bfs
class Solution {
public:
    vector<int> rightSideView(TreeNode *root) {
        vector<int> res;
        if (!root) return res;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            int s = q.size();
            for (int i = 0; i < s; i++) {
                TreeNode *p = q.front();
                q.pop();
                if (i == s - 1) res.push_back(p->val);
                if (p->left) q.push(p->left);
                if (p->right) q.push(p->right);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

31、树的子结构

Leetcode Offer 26

class Solution {
public:
    bool dfs(TreeNode *A, TreeNode *B) {
        if (!B) return true;
        if (!A || A->val != B->val) return false;
        return dfs(A->left, B->left) && dfs(A->right, B->right);
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (!A || !B) return false;
        return dfs(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13