二叉树的堂兄弟节点 II 图解题解

这道题到底在问什么

输入

root=[5,4,9,1,10,null,7]

输出

[0,0,0,7,7,null,11]

输入

root=[3,1,2]

输出

[0,0,0]

最优解：一步一步想明白

1. 3记牢这一句:堂兄弟和 = 本层总和 减去 同父那一组的和。下面先把三层的总和算出来,再自上而下一个父亲一个父亲地发放。
2. 4原始输入这是初始的树,层序是 5,4,9,1,10,空,7。根 5 在第 0 层,4 和 9 在第 1 层,1、10、7 在第 2 层。我们的目标,是把每个节点的值,换成它所有堂兄弟节点的值之和。先把「谁和谁是堂兄弟」看清楚。
3. 51 和 10 是亲兄弟 · 7 是它们的堂兄弟看第 2 层这三个节点。1 和 10 的父亲都是 4,它俩是亲兄弟,不算堂兄弟。7 的父亲是 9,和 1、10 的父亲不一样。所以 7 与 1、10 才互为堂兄弟。抓住这个区别:同一层还不够,必须父亲不同。
4. 6第 0 层只有根 5第一趟自上而下,把每一层的总和都求出来。第 0 层只有根节点 5,这一层的总和就是 5。记到右边面板里。
5. 7第 1 层是 4 和 9第 1 层有 4 和 9 两个节点,它们相加是 13,这就是第 1 层的总和。注意这一层里 4 和 9 是亲兄弟,同一个父亲根 5 底下。
6. 8第 2 层是 1, 10, 7第 2 层有 1、10、7 三个节点,相加是 18。三层的总和都算好了,分别是 5、13、18。第一趟到此结束,接下来第二趟开始发放。
7. 94 底下是一组亲兄弟发放前先把「同父的组」看清楚。节点 4 底下的 1 和 10 是一组亲兄弟。等下算这两个孩子的堂兄弟和时,要从第 2 层总和里减掉的,正是这一组 1 加 10。
8. 109 底下只有一个孩子节点 9 底下只有右孩子 7,左孩子是空的。所以 9 名下这一组就只有 7 自己。等下算 7 的堂兄弟和,要减掉的就是它自己这一格。
9. 11根在第 0 层,孤零零一个第二趟自上而下发放。先看根 5。它在第 0 层,整层就它一个,没有任何同层的伙伴,自然也没有堂兄弟。所以它的堂兄弟和是 0。
10. 12根 5 → 0把根改写成 0。注意这一改不影响后面的计算,因为算孩子时用的是孩子那一层的原始值,和根现在是几没关系。接着往下一层发放。
11. 134 和 9 是同父亲(根)的一组看根的两个孩子 4 和 9。它俩同层,而且同一个父亲根,是一组亲兄弟。它们所在的第 1 层总和是 13。堂兄弟和,就要拿这个 13 去减掉它们这一组自己的和。
12. 144 和 9 各自的堂兄弟和4 和 9 这一组自己的和是 4 加 9 等于 13,恰好等于整层总和 13。相减得到 0,说明它们在这一层里没有别的父亲的伙伴。所以 4 和 9 的堂兄弟和都是 0。
13. 15第 1 层发放完毕把 4 和 9 都改写成 0。第 1 层发放完毕。继续往下,进入第 2 层,分别由 4 和 9 这两个父亲来发放。
14. 161 和 10 是同父的一组轮到左边这个父亲,它原来的值是 4,现在已经是 0 了。它名下有 1 和 10 两个孩子,都在第 2 层。第 2 层总和是 18,接下来拿它减掉 1 和 10 这一组自己的和。
15. 171 和 10 各自的堂兄弟和1 和 10 这一组自己的和是 1 加 10 等于 11。第 2 层总和 18 减去 11,得到 7。这个 7 就是它俩在第 2 层里、别的父亲那几个孩子的和,也就是它们唯一的堂兄弟 7。所以 1 和 10 都改成 7。
16. 18左支的孩子发放完毕把 1 和 10 都改写成 7,和我们一开始说的答案对上了。左边这个父亲名下的孩子处理完,只剩右边父亲名下那个 7 了。
17. 19左孩子是空的轮到右边这个父亲,它原来是 9,现在也是 0 了。它只有右孩子 7,左孩子是空的。算 7 的堂兄弟和时,要从第 2 层总和里减掉的,就是这个父亲名下的孩子之和,也就是 7 自己加上空的那半边算 0。
18. 207 的堂兄弟和这个父亲名下的孩子之和是 0 加 7 等于 7。第 2 层总和 18 减去 7,得到 11。这个 11 正好是 7 在第 2 层里的两个堂兄弟 1 和 10 之和。所以 7 改成 11。
19. 21所有节点发放完毕把 7 改写成 11。至此,除根之外每个节点都拿到了它的堂兄弟之和,整棵树发放完毕。下面回头验一遍。
20. 22结果 = [0,0,0,7,7,null,11]最终这棵树的层序变成 0、0、0、7、7、空、11。和官方给的答案一模一样。回顾一下每一步都在做同一件事:本层总和,减去同父那一组的和。
21. 23逐点检验堂兄弟关系逐个检验。节点 1 在第 2 层,同层里父亲不同的只有 7,所以它的堂兄弟和是 7,对得上。10 同理,堂兄弟也只有 7,改成 7。7 的堂兄弟是 1 和 10,和为 11,也对得上。根和第 1 层没有堂兄弟,全归 0。全部吻合。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs1(root: Optional[TreeNode], depth: int):
            if root is None:
                return
            if len(s) <= depth:
                s.append(0)
            s[depth] += root.val
            dfs1(root.left, depth + 1)
            dfs1(root.right, depth + 1)

        def dfs2(root: Optional[TreeNode], depth: int):
            sub = (root.left.val if root.left else 0) + (
                root.right.val if root.right else 0
            )
            depth += 1
            if root.left:
                root.left.val = s[depth] - sub
                dfs2(root.left, depth)
            if root.right:
                root.right.val = s[depth] - sub
                dfs2(root.right, depth)

        s = []
        dfs1(root, 0)
        root.val = 0
        dfs2(root, 0)
        return root

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* replaceValueInTree(TreeNode* root) {
        memset(s, 0, sizeof(s));
        dfs1(root, 0);
        root->val = 0;
        dfs2(root, 0);
        return root;
    }

private:
    int s[100010];
    void dfs1(TreeNode* root, int depth) {
        if (!root) {
            return;
        }
        s[depth] += root->val;
        dfs1(root->left, depth + 1);
        dfs1(root->right, depth + 1);
    };

    void dfs2(TreeNode* root, int depth) {
        int l = root->left ? root->left->val : 0;
        int r = root->right ? root->right->val : 0;
        int sub = l + r;
        ++depth;
        if (root->left) {
            root->left->val = s[depth] - sub;
            dfs2(root->left, depth);
        }
        if (root->right) {
            root->right->val = s[depth] - sub;
            dfs2(root->right, depth);
        }
    };
};

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private List<Integer> s = new ArrayList<>();

    public TreeNode replaceValueInTree(TreeNode root) {
        dfs1(root, 0);
        root.val = 0;
        dfs2(root, 0);
        return root;
    }

    private void dfs1(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        if (s.size() <= depth) {
            s.add(0);
        }
        s.set(depth, s.get(depth) + root.val);
        dfs1(root.left, depth + 1);
        dfs1(root.right, depth + 1);
    }

    private void dfs2(TreeNode root, int depth) {
        int l = root.left == null ? 0 : root.left.val;
        int r = root.right == null ? 0 : root.right.val;
        int sub = l + r;
        ++depth;
        if (root.left != null) {
            root.left.val = s.get(depth) - sub;
            dfs2(root.left, depth);
        }
        if (root.right != null) {
            root.right.val = s.get(depth) - sub;
            dfs2(root.right, depth);
        }
    }
}

复杂度

面试官可能追问