二叉树累加和的最长路径

CD165 在二叉树中找到累加和为指定值的最长路径长度

写的好心酸, 明明只有有类似的题目接触到。又是没思考就动手

  • 先静态化构造二叉树(不要嫌麻烦,一题写好了所有题目都可以用)

  • 前序遍历节点,

    • 记录根节点到当前节点的综合newadd,只记录最短长度的newadd路径。
    • 同时判断,newadd - target之和是否有在当前遍历路径下,是否存在从根节点到同路径的某个节点连成的路径。
    • 最后回溯时,为了下次遍历路径不受这里遍历数据影响,消减掉当次遍历时候设置新路径长度。

代码


#include <bits/stdc++.h>
using namespace std;

// initialize binary tree
struct node {
    int val;
    node* left;
    node* right;
};

int n, rootIdx;
node* tree;
node* build() {
    cin >> n >> rootIdx;
   node* tree = new node[n + 1];
    for(int i = 0; i < n; ++i) {
        int v, r, l, x;
        cin >> v >> l >> r >> x;
        tree[v] = node{x, &(tree[l]), &(tree[r])};
        if(l == 0) tree[v].left = nullptr;
        if(r == 0) tree[v].right = nullptr;
        
    }
    return &tree[rootIdx];
}


void clear() {
    delete tree;
}

//my code in here

unordered_map<int, int> longest;

void findLongest(node *root, int add, int target, int len, int &maxlen) {
    if(root == nullptr) return;
    int newadd = add + root->val;
    bool isset = false;
    if(longest[newadd] == 0) {
        longest[newadd] = len;
        isset = true;
    }
    int cntlen = longest[newadd - target];
    if(cntlen > 0) { 
        maxlen = max(maxlen, len - cntlen);
    }
  
    findLongest(root->right, newadd, target, len + 1, maxlen),
    findLongest(root->left, newadd, target, len + 1, maxlen);
    if(isset) longest[newadd] = 0;
}


int main() {
    node* root = build();
    int target;
    cin >> target;
    int maxlen = 0;
    longest[0] = 1;
    findLongest(root, 0,  target, 2, maxlen);
    cout << maxlen;
    clear();
}

Comments