二叉树问题通常有个dfs函数，该函数返回一个值、用引用参数修改另一个值。

回溯的参数是传值时，相当于自动在调用后做了参数还原；回溯的参数是引用时，要在调用后做参数还原。

值唯一的子树个数

int countUnivalSubtrees(TreeNode* root) {
    int ans = 0;
    isUnivalue(root, ans);
    return ans;
}

bool isUnivalue(TreeNode *root, int &ans) {
    if (!root) return true;

    auto left = isUnivalue(root->left, ans);
    auto right = isUnivalue(root->right, ans);
    if (!left || (root->left && root->left->val != root->val)) return false;
    if (!right || (root->right && root->right->val != root->val)) return false;

    ans++;
    return true;
}

N枚硬币不均匀散布在二叉树中，每次可在父子间移动一枚硬币，要让硬币均匀分布，需要几次移动

int distributeCoins(TreeNode* root) {
    int ans = 0;
    excessCoins(root, ans);
    return ans;
}

// 返回：某子树有多少多余硬币
int excessCoins(TreeNode *root, int &ans) {
    if (!root) return 0;
    auto left = excessCoins(root->left, ans);
    auto right = excessCoins(root->right, ans);
    ans += abs(left) + abs(right); // 在本节点和左右子节点间移动多余硬币
    return left + right + root->val - 1;
}

祖父节点是偶数的所有节点之和

int sumEvenGrandparent(TreeNode* root) {
    int ans = 0;
    dfs(root, false, false, ans);
    return ans;
}

void dfs(TreeNode *root, bool pEven, bool gpEven, int &ans) {
    if (!root) return;
    if (gpEven) ans += root->val;
    bool even = root->val % 2 == 0;
    dfs(root->left, even, pEven, ans);
    dfs(root->right, even, pEven, ans);
}

最大的层宽度

  • https://leetcode.com/problems/maximum-width-of-binary-tree/
int widthOfBinaryTree(TreeNode* root) {
    int ans = INT_MIN;
    vector<int> leftMost; // 各层最左节点的id 
    dfs(root, 0, 1, leftMost, ans);
    return ans;
}

void dfs(TreeNode *root, int depth, int id, vector<int> &leftMost, int &ans) {
    if (!root) return;
    if (depth == leftMost.size()) leftMost.push_back(id);

    ans = max(ans, id - leftMost[depth] + 1);
    dfs(root->left, depth + 1, id * 2, leftMost, ans);
    dfs(root->right, depth + 1, id * 2 + 1, leftMost, ans);
}

分成等和的两树

Given a binary tree with n nodes, your task is to check if it's possible to partition the tree to two trees which have the equal sum of values after removing exactly one edge on the original tree.

Example 1:

Input:     
    5
   / \
  10 10
    /  \
   2   3

Output: True
Explanation: 
    5
   / 
  10
      
Sum: 15

   10
  /  \
 2    3

Sum: 15

Example 2:

Input:     
    1
   / \
  2  10
    /  \
   2   20

Output: False
Explanation: You can't split the tree into two trees with equal sum after removing exactly one edge on the tree.

bool checkEqualTree(TreeNode* root) {
    unordered_map<int, int> mp; // sum=>count
    int sum = getSum(root, mp);
    if (sum == 0) return mp[0] > 1;
    return sum % 2 == 0 && mp.count(sum / 2);
}

int getSum(TreeNode *root, unordered_map<int, int> &mp) {
    if (!root) return 0;
    int sum = root->val + getSum(root->left, mp) + getSum(root->right, mp);
    mp[sum]++;
    return sum;
}

可返回随机节点的二叉树

每个节点知道以自己为根的子树size，这就是顺序统计树，可以O(lgn)时间找第k个节点。

顺序统计树参考：

public class RankNode {
    public int data;
    public RankNode left, right;
    public int size = 1;
    public RankNode(int d) {
        data = d;
    }

    public void insert(int d) {
        if (d <= data) {
            if (left != null) left.insert(d);
            else left = new RankNode(d);
        } else {
            if (right != null) right.insert(d);
            else right = new RankNode(d);
        }
        size++;
    }

    int getRank(int d) { // 0-based
        if (d == data) {
            return left == null ? 0 : left.size();
        } else if (d < data) {
            return left == null ? -1 : left.getRank(d);
        } else {
            int rightRank = right == null ? -1 : right.getRank(d);
            if (rightRank == -1) return -1; // 要这么写，因为right.getRank()可能返回-1
            int leftSize = left == null ? 0 : left.size();
            return leftSize + 1 + rightRank;
        }
    }
}

类似的，见ctci p413

节点上的相机可看到节点本身、相连的父节点和子节点，为看到全树最少装多少相机

class Solution {
    const int NO_CAMERA_NOT_COVERED = 0;
    const int NO_CAMERA_BUT_COVERED = 1;
    const int CAMERA_HERE = 2;
public:
    int minCameraCover(TreeNode* root) {
        int ans = 0;
        if (dfs(root, ans) == NO_CAMERA_NOT_COVERED) ans++;
        return ans;
    }

    int dfs(TreeNode *root, int &ans) {
        if (!root) return NO_CAMERA_BUT_COVERED;
        int left = dfs(root->left, ans), right = dfs(root->right, ans);

        if (left == NO_CAMERA_NOT_COVERED || right == NO_CAMERA_NOT_COVERED) {
            ans++;
            return CAMERA_HERE;
        }
        if (left == CAMERA_HERE || right == CAMERA_HERE) {
            return NO_CAMERA_BUT_COVERED;
        }
        return NO_CAMERA_NOT_COVERED;
    }
};

路径的排列是回文

int pseudoPalindromicPaths(TreeNode* root) {
    // 用count的第i位记录数字x的奇偶，1<=x<=9
    int count = 0, ans = 0;
    dfs(root, count, ans);
    return ans;
}

void dfs(TreeNode *root, int count, int &ans) {
    if (!root) return;
    count ^= (1 << root->val);
    if (!root->left && !root->right) {
        ans += (count & (count - 1)) == 0; // 最多1位1
    }
    
    dfs(root->left, count, ans);
    dfs(root->right, count, ans);
}