二叉树属性求解

二叉树宽度

节点最多的一层的节点数

也有时定义为最左节点和最右节点之间的距离（含空节点），暂不讨论。

求法

层序遍历，每层统计节点数，取最大值

int width(Node root){
    // 空树宽度为0
    if(root == null) return 0;
    // 层序遍历
    queue<Node> q;
    q.push(root);
    int w = 0;
    while(!q.empty()){
        // 当前层节点数
        int size = q.size();
        // 更新最大宽度
        w = max(w, size);
        // 遍历当前层所有节点
        for(int i = 0; i < size; i++){
            Node node = q.front();
            q.pop();
            if(node.left) q.push(node.left);
            if(node.right) q.push(node.right);
        }
    }
    return w;
}

二叉树深度

根节点到叶子节点的最长路径上的节点数。

dfs求法

递归求解左右子树的深度，取最大值加1（当前节点）

int depth(Node root){
    //  到达空子树
    if(root == null) return 0;
    // 求左右子树的深度
    int left = depth(root.left);
    int right = depth(root.right);
    // 取最大 + 1（当前节点）
    return max(left, right) + 1;
}

bfs求法

层序遍历，每完成一层，深度加1，直到遍历完所有层

int depth(Node root){
    // 空树深度为0
    if(root == null) return 0;
    // 层序遍历
    queue<Node> q;
    q.push(root);
    int depth = 0;
    while(!q.empty()){
        // 当前层节点数
        int size = q.size();
        // 遍历当前层所有节点
        for(int i = 0; i < size; i++){
            Node node = q.front();
            q.pop();
            if(node.left) q.push(node.left);
            if(node.right) q.push(node.right);
        }
        // 完成一层，深度加1
        depth++;
    }
    return depth;
}

节点深度

从根节点到目标节点路径上的节点数

单个求法

从根节点出发，在左右子树中寻找目标节点，记录步数

int depth(Node root, Node tar, int d){
    // 到头了，没找到
    if(root == null) return -1;
    // 找到目标节点，返回步数
    if(root == tar) return d;
    // 在左子树中寻找
    int left = depth(root.left, tar, d + 1);
    // 如果在左子树找到，直接返回
    if(left != -1) return left;
    // 在右子树中寻找
    return depth(root.right, tar, d + 1);
}

批量求法

从根节点出发，每层深度+1，全部记录

// 全局map记录所有节点的深度
unordered_map<Node, int> all_depth;
void depth(Node root, int d){
    // 到达空节点，返回
    if(root == null) return;
    // 记录当前节点深度
    all_depth[root] = d;
    // 在左右子树中继续记录，深度+1
    depth(root.left, d + 1);
    // 右子树，深度同样+1
    depth(root.right, d + 1);
}

最近公共祖先（LCA）

从根节点到目标节点的路径上，深度最大的公共节点

暴力求法

分别求路径，遍历两条路径，找到最后一个相同的节点

bool findPath(Node root, Node tar, vector<Node> &path){
    // 根节点加入路径
    path.push_back(root);
    // 找到目标节点，返回true
    if(root == tar) return true;
    // 在左子树继续寻找
    if(root.left && findPath(root.left, tar, path)) return true;
    // 在右子树继续寻找
    if(root.right && findPath(root.right, tar, path)) return true;
    // 没找到，回退路径
    path.pop_back();
    return false;
}
Node lca(Node root, Node u, Node v){
    // 求路径
    vector<Node> pathU, pathV;
    findPath(root, u, pathU);
    findPath(root, v, pathV);
    // 遍历两条路径，找到最后一个相同的节点
    Node res = null;
    for(int i = 0; i < min(pathU.size(), pathV.size()); i++){
        if(pathU[i] == pathV[i]) res = pathU[i];
        else break;
    }
    return res;
}

递归求法

在左右子树中找LCA，两边都找到，当前节点就是LCA

Node lca(Node root, Node u, Node v){
    // 根节点为空，返回null
    if(root == null) return null;
    // 找到目标节点，返回当前节点
    if(root == u || root == v) return root;
    // 在左右子树继续寻找
    Node left = lca(root.left, u, v);
    Node right = lca(root.right, u, v);
    // 两边都找到，当前节点就是LCA
    if(left && right) return root;
    // 一边找到，返回LCA存在的一边
    if(left) return left;
    if(right) return right;
    // 没找到，返回null
    return null;
}

节点距离

两节点之间最短路径的边数

也有时候定义为节点数，$+1$ 即可

lca深度法

求两节点和LCA的深度，距离即为两节点深度之和减去LCA深度的两倍

$dist(u, v) = depth(u) + depth(v) - 2 \times depth(lca)$

int dist(Node root, Node u, Node v){
    Node LCA = lca(root, u, v);
    // 注意depth是节点深度函数，不是树深度函数
    return depth(u) + depth(v) - 2 * depth(LCA);
}

lca距离法

求两节点到LCA的距离，距离和即为两节点之间的距离

$dist(u, v) = dist(u, lca) + dist(v, lca)$

int ans = -1; // 全局变量记录距离
int dist(Node root, Node u, Node v){
    // 空节点
    if(root == null) return -1;
    // 递归左右子树
    int left = dist(root.left, u, v);
    int right = dist(root.right, u, v);
    // 当前节点是目标
    if(root == u || root == v){
        // 如果有一边找到另一目标，当前目标为LCA
        if(left != -1 || right != -1) return max(left, right) + 1;
        // 否则两目标相同，距离为0
        return 0;
    }
    // 两边都找到，当前节点为LCA
    if(left != -1 && right != -1) {
        // 距离为两边距离之和 + 2（当前节点到两目标的边数）
        ans = left + right + 2;
        return ans;
    }
    // 只有一边找到
    if(left != -1) return left + 1;
    if(right != -1) return right + 1;
    // 没找到
    return -1;
}