关于树的深度、直径和路径

总结了关于树的路径问题，包括树的深度、树的直径、树的路径等。

树的深度

树的最大深度

• 问题描述

如二叉树的最大深度所描述：

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

• 问题分析

1. 利用深度优先搜索，分别求出左右两棵子树的最大深度，再取左右子树最大深度的最大值加一（子树的父节点也有深度）。
2. 利用广度优先搜索，维护一个整数结果，一层一层进行遍历，每遍历一层结果加一。

• 代码实现

1. 深度优先搜索

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        int left = maxDepth(root->left), right = maxDepth(root->right);
        return max(left, right) + 1;
    }
};

1. 广度优先搜索

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int ans = 0;
        while (!q.empty()) {
            int len = q.size();
            // 分层遍历
            while (len --) {
                TreeNode* t = q.front();
                q.pop();
                if (t->right) q.push(t->right);
                if (t->left) q.push(t->left);
            }
            ans ++;
        }
        return ans;
    }
};

树的最小深度

• 问题描述

如二叉树的最小深度所描述：

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

• 问题分析

1. 利用深度优先搜索，分情况讨论：节点为空；左右节点都存在；左右节点都不存在；左节点存在；右节点存在。
2. 利用广度优先搜索，分层遍历，第一次遍历到左右节点都为空时，停止遍历，返回结果。

• 代码实现

1. 深度优先搜索

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        if (!root->right && !root->left) return 1;
        if (root->right && root->left) return min(minDepth(root->right), minDepth(root->left)) + 1;
        if (root->right) return minDepth(root->right) + 1;
        return minDepth(root->left) + 1;
    }
};

1. 广度优先搜索

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int ans = 0;
        while (!q.empty()) {
            ans ++;
            int len = q.size();
            while (len --) {
                TreeNode* t = q.front();
                q.pop();
                if (!t->left && !t->right) return ans;
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
        }
        return ans;
    }
};

树的直径

一般解法步骤

• 边权为正

1. 任取一点作为起点，找到距离该点最远的一个点u。
2. 再找到距离点u最远的一个点v。
3. 点u与点v之间的路径就是一条直径。

证明过程：树的最长路径

• 边权正负不确定

利用树形DP，以任一节点为根节点，求出该节点所有子树的最长路径，再从该节点的所有子树中取最长路径与次最长路径相加，即为树的直径。

不带边权的树的直径

• 问题描述

如二叉树的直径所描述：

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个节点路径长度中的最大值。这条路径可能穿过也可能不穿过根节点。

• 问题分析

利用树形DP，维护一个整数ans，表示经过当前节点的最长路径，分别对左右两棵子树进行遍历，并在遍历过程中动态更新 ans。

• 代码实现

class Solution {
public:
    int ans = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return ans;
    }

    int dfs(TreeNode* root) {
        if (!root) return 0;
        auto left = dfs(root->left), right = dfs(root->right);
        ans = max(ans, left + right);
        // 该返回可以有两种解释：
        // 1. 以当前节点为根节点，经过当前节点与树的叶子节点的最长路径的节点个数
        // 2. 以当前节点为根节点的子树的深度
        return max(left, right) + 1;
    }
};

带边权的树的直径

• 问题描述

如树的最长路径所描述：

给定一棵树，树中包含n个节点（编号1~n）和n−1条无向边，每条边都有一个权值。

现在请你找到树中的一条最长路径。

换句话说，要找到一条路径，使得使得路径两端的点的距离最远。

注意：路径中可以只包含一个点。

• 问题分析

与上题类似，利用树形DP，维护一个整数ans，表示经过当前节点的最长路径，分别对当前节点的所有子树进行遍历，获取当前节点到叶子节点的最长路径和次最长路径，并在遍历过程中动态更新 ans。

• 代码实现

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010, M = N * 2;
int n;
int h[N], e[M], ne[M], w[M], idx;
int ans;

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

int dfs(int u, int father) {
    int dist = 0;    // 表示当前节点到叶子节点的最长路径（与d1含义一致，可省略）
    int d1 = 0, d2 = 0;    // 保存到当前节点到叶子节点的最长路径和次最长路径
    for (int i = h[u]; ~i; i = ne[i]) {
        int t = e[i];
        if (t == father) continue;
        int d = dfs(t, u) + w[i];    // 获取该子树的最长路径
        dist = max(dist, d);
        // 更新当前节点到叶子节点的最长路径和次最长路径
        if (d >= d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }
    ans = max(ans, d1 + d2);
    return dist;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n;
    int a, b, c;
    
    for (int i = 0; i < n - 1; i ++) {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    
    dfs(1, -1);
    cout << ans << endl;
    return 0;
}

• 相似题目

  二叉树中的最大路径和：

  class Solution {
  public:
      int res = INT_MIN;
      int maxPathSum(TreeNode* root) {
          dfs(root);
          return res;
      }
  
      int dfs(TreeNode* root) {
          if (!root) return 0;
          int dist = 0;
          int left = dfs(root->left), right = dfs(root->right);
          dist = max(dist, max(left, right) + root->val);
          res = max(res, left + right + root->val);
          return dist;
      }
  };

树的路径

根节点到叶子节点的路径

所有路径

• 问题描述

如二叉树的所有路径所描述：

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

• 问题分析

深搜即可。

• 代码实现

class Solution {
public:
    vector<int> path;
    vector<string> res;
    vector<string> binaryTreePaths(TreeNode* root) {
        dfs(root);
        return res;
    }

    void dfs(TreeNode* root) {
        path.push_back(root->val);
        if (!root->right && !root->left) {
            res.push_back(getPathStr());
        } else {
            if (root->left) dfs(root->left);
            if (root->right) dfs(root->right);
        }
        path.pop_back();
    }

    string getPathStr() {
        string str = to_string(path[0]);
        for (int i = 1; i < path.size(); i ++) {
            str += "->" + to_string(path[i]);
        }
        return str;
    }
};

和为某个值的路径

• 问题描述

如路径总和所描述：

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

• 问题分析

深搜即可。

• 代码实现

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;	// 若为空节点
        if (!root->left && !root->right) {	// 若为叶子节点
            if (targetSum == root->val) return true;
            return false;
        }
        return hasPathSum(root->right, targetSum - root->val) || hasPathSum(root->left, targetSum - root->val);
    }
};

经过某条边的最长路径

• 问题描述

如必经之路所描述：

题目内容：

塔子哥的班主任最近组织了一次户外拓展活动，让班里的同学们一起去爬山。在路上，塔子哥看到了一棵漂亮的树，他对这棵树产生了浓厚的兴趣，开始观察并记录这棵树的一些特征。

塔子哥发现这棵树有n个节点，其中有一条边被特别标记了出来。他开始思考这条特殊的边在树上起到了什么样的作用，于是他想知道，经过这条选定边的所有树上简单路径中，最长的那条路径有多长，以便更好地理解这棵树的结构。

一条简单的路径的长度指这条简单路径上的边的个数。

输入描述：

第一行一个整数$n$，表示树的节点个数。

第二行$n-1$个整数，第$i$个数表示节点$i+1$和$p_i$之间有一条边相连。

第三行两个整数$x$，$y$，表示这条选定的边。保证这条边一定是树上的一条边。

对于全部数据，$2\leq n \leq 10^5$ ，$1\leq p_i \leq n$ ，$1\leq x,y \leq n$，$x\neq y$ 。

保证输入数据正确描述一棵树，并且$(x,y)$是树上的条边。

样例：

输入：

7
1 2 3 4 5 3
3 7

输出：

4

• 问题分析

将树以$(x,y)$为边一分为二，分别求出以$x$和$y$为根节点的最长路径，再相加即可。

• 代码实现

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 2 * N;
int n, x, y;
int h[N], e[M], ne[M], idx;

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

int dfs(int u, int father) {
  int dist = 0;
  // 遍历该节点的所有子节点
  for (int i = h[u]; ~i; i = ne[i]) {
      int j = e[i];
      if (j == father) continue;
      dist = max(dist, dfs(j, u));
  }
  return dist + 1;
}

int main() {
  memset(h, -1, sizeof h);
  cin >> n;
  int p;
  for (int i = 1; i < n; i ++) {
      scanf("%d", &p);
      add(i + 1, p), add(p, i + 1);
  }
  cin >> x >> y;
  int x_dist = dfs(x, y) - 1;  // 以x为根的子树最长路径
  int y_dist = dfs(y, x) - 1;  // 以y为根的子树最长路径
  cout << x_dist + y_dist + 1 << endl;  // 加上x，y之间的路径1
  return 0;
}