algo-aha

经过单一值的最大边数

• https://leetcode.com/problems/longest-univalue-path/

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

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

    int leftEdge = 0, rightEdge = 0;
    if (root->left && root->left->val == root->val) leftEdge = 1 + left;
    if (root->right && root->right->val == root->val) rightEdge = 1 + right;
    ans = max(ans, leftEdge + rightEdge); // 经过当前节点的最大边数

    return max(leftEdge, rightEdge);
}

二叉树的直径

• https://leetcode.com/problems/diameter-of-binary-tree/

int diameterOfBinaryTree(TreeNode* root) {
    int ans = 0;
    dfs(root, ans);
    return ans;
}
    
int dfs(TreeNode *root, int &ans) {
    if (!root) return 0;

    int left = dfs(root->left, ans);
    int right = dfs(root->right, ans);
    ans = max(ans, left + right); // 经过当前节点的直径长

    return 1 + max(left, right);
}

沿路径向下的最大节点差值

• https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/

int maxAncestorDiff(TreeNode* root) {
    int ans = 0;
    dfs(root, INT_MAX, INT_MIN, ans);
    return ans;
}

void dfs(TreeNode *root, int mn, int mx, int &ans) {
    if (!root) return;
    mn = min(mn, root->val);
    mx = max(mx, root->val);
    dfs(root->left, mn, mx, ans);
    dfs(root->right, mn, mx, ans);
    ans = max(ans, mx - mn);
}

最长连续递增的向下路径

• https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/

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

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

    int len = 1;
    if (root->left && root->left->val == root->val + 1)
        len = max(len, 1 + left);
    if (root->right && root->right->val == root->val + 1)
        len = max(len, 1 + right);
    ans = max(ans, len);
    return len;
}

最长连续递增或递减的任意路径

• https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/

Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree.

Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid. On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:

Input:
        1
       / \
      2   3
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].

Example 2:

Input:
        2
       / \
      1   3
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].

Note: All the values of tree nodes are in the range of [-1e7, 1e7].

class Solution {
    struct Info {
        int incCnt;
        int decCnt;
    };
public:
    int longestConsecutive(TreeNode* root) {
        int ans = 0;
        dfs(root, ans);
        return ans;
    }
    
    // 从root开始往下递增和递减的节点数
    Info dfs(TreeNode *root, int &ans) {
        if (!root) return {0, 0};
        auto left = dfs(root->left, ans);
        auto right = dfs(root->right, ans);

        int incCnt = 1, decCnt = 1;        
        if (root->left) {
            if (root->left->val == root->val + 1) {
                incCnt = max(incCnt, left.incCnt + 1);
            } else if (root->left->val == root->val - 1) {
                decCnt = max(decCnt, left.decCnt + 1);
            }
        }
        if (root->right) {
            if (root->right->val == root->val + 1) {
                incCnt = max(incCnt, right.incCnt + 1);
            } else if (root->right->val == root->val - 1) {
                decCnt = max(decCnt, right.decCnt + 1);
            }
        }
        ans = max(ans, incCnt + decCnt - 1);
        return {incCnt, decCnt};
    }
};

最长ZigZag向下路径长

• https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/

int longestZigZag(TreeNode* root) {
    return dfs(root)[2];
}

// 返回{leftLongest, rightLongest, subLongest}
// 表示从当前节点向左最长、向右最长，当前子树所含最长
array<int,3> dfs(TreeNode *root) {
    if (!root) return {-1,-1,-1};
    auto left = dfs(root->left);
    auto right = dfs(root->right);
    int toL = 1 + left[1], toR = 1 + right[0];
    int sub = max({toL, toR, left[2], right[2]});
    return { toL, toR, sub };
}