543-二叉树的直径

LeetCode

发布日期: 2022-02-22

LeetCode 543. Diameter of Binary Tree

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

method

假设左子树高度为L，右子树高度为R，则直径为L+R+1

int res = 0;
int traversal(TreeNode *root) {
    if (!root) return 0;
    int leftDepth = traversal(root->left);
    int rightDepth = traversal(root->right);
    res = max(res, leftDepth + rightDepth);
    return max(leftDepth, rightDepth) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
    traversal(root); 
    return res;
}

LeetCode 1522. N 叉树的直径

给定一棵 N 叉树的根节点 root ，计算这棵树的直径长度。

N 叉树的直径指的是树中任意两个节点间路径中最长路径的长度。这条路径可能经过根节点，也可能不经过根节点。

（N 叉树的输入序列以层序遍历的形式给出，每组子节点用 null 分隔）

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：3

method

记录最大高度和第二大高度就行

int res;
int dfs(Node *root) {
    if (!root) return 0;
    int max1 = 0, max2 = 0;
    for (int i = 0; i < root->children.size(); i++) {
        int depth = dfs(root->children[i]);
        if (depth > max1) {
            max2 = max1;
            max1 = depth;
        } else if (depth > max2) {
            max2 = depth;
        }
    }
    res = max(res, max1 + max2);
    return 1 + max1;
}
int diameter(Node* root) {
    dfs(root);
    return res;
}

LeetCode 687. 最长同值路径

给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。这条路径可以经过也可以不经过根节点。

两个节点之间的路径长度 由它们之间的边数表示。

示例 1:

输入：root = [5,4,5,1,1,5]
输出：2

method

后序遍历看左右子树满足条件有多少个，再看当前节点

如果当前节点与左子树相同，则curLeft=leftNum+1
如果当前节点与右子树相同，则curRight=rightNum+1

用curLeft+curRight更新res，用max(curLeft, curRight)返回给上一层

int res = 0;
int dfs(TreeNode *root) {
    if (!root) return 0;
    int leftNum = dfs(root->left);
    int rightNum = dfs(root->right);
    int curLeft = 0, curRight = 0;
    if (root->left && root->left->val == root->val) {
        curLeft = leftNum + 1;
    }
    if (root->right && root->right->val == root->val) {
        curRight = rightNum + 1;
    }
    res = max(res, curLeft + curRight);
    return max(curLeft, curRight);
}
int longestUnivaluePath(TreeNode* root) {
    dfs(root);
    return res;
}

LeetCode 298. 二叉树最长连续序列

给你一棵指定的二叉树的根节点 root ，请你计算其中 最长连续序列路径 的长度。

最长连续序列路径 是依次递增 1 的路径。该路径，可以是从某个初始节点到树中任意节点，通过「父 - 子」关系连接而产生的任意路径。且必须从父节点到子节点，反过来是不可以的。

示例 1：

输入：root = [1,null,3,2,4,null,null,null,5]
输出：3
解释：当中，最长连续序列是 3-4-5 ，所以返回结果为 3 。

method

跟上题一样的后序套路

int res;
int dfs(TreeNode *root) {
    if (!root) return 0;
    int leftNum = dfs(root->left);
    int rightNum = dfs(root->right);
    int curLeft = 0, curRight = 0;
    if (root->left && root->left->val == root->val + 1) curLeft = leftNum + 1;
    if (root->right && root->right->val == root->val + 1) curRight = rightNum + 1;
    res = max(res, max(curLeft, curRight) + 1);
    return max(curLeft, curRight);
}
int longestConsecutive(TreeNode* root) {
    dfs(root);
    return res;
}