给定二叉树头结点和sum,打印等于sum的最长路径长度
输入：
{-3,3,-9,1,0,2,1,0,0,1,6,0,0}
6
输出：
4
// // main.cpp // 在二叉树中找到累加和为指定值的最长路径长度 // // Created by zjl on 16/9/14. // Copyright © 2016年 zjl. All rights reserved. // 一条符合指定值的路径可以从任何节点开始，同时也可以跳过某些路径上的节点 #include <iostream> #include <vector> #include <queue> #include <map> using namespace std; struct TreeNode{ int val; TreeNode* left; TreeNode* right; TreeNode(int x):val(x),left(NULL),right(NULL){} }; //初始化是层次遍历的初始化过程 TreeNode* create(vector<int>vec){ int num = vec.size(); TreeNode* root = new TreeNode(vec[0]); queue<TreeNode*> q; q.push(root); int i = 1; while(i <= num){ TreeNode* t = q.front(); q.pop(); if(vec[i] > 0){ t->left = new TreeNode(vec[i]); q.push(t->left); } else t->left = NULL; i++; if(i<= num){ if(vec[i] > 0){ t->right = new TreeNode(vec[i]); q.push(t->right); } else t->right = NULL; i++; } } return root; } int preorder(TreeNode* root, int sum, int presum, int level, int maxlen, map<int, int>&mp){ if(root == NULL) return maxlen; int cursum = presum + root->val; if(mp.find(cursum) == mp.end()) mp[cursum] = level; if(mp.find(cursum - sum) != mp.end()) maxlen = max(maxlen, level - mp[cursum-sum]); maxlen = preorder(root->left, sum, cursum, level+1, maxlen, mp); maxlen = preorder(root->right, sum, cursum, level+1, maxlen, mp); if(level == mp[cursum]) mp.erase(cursum); return maxlen; } int solve(TreeNode* root, int sum){ map<int, int>mp; mp[0] = 0; //记录目前的路径总和，对应的层数 return preorder(root, sum, 0, 1, 0, mp); } int main(int argc, const char * argv[]) { // insert code here... vector<int>num={-3,3,-9,1,0,2,1,0,0,1,6,0,0};//这里，0->NULL TreeNode* root = create(num); int sum = 6; //指定值 int res = solve(root, sum); cout<< res<<endl; return 0; }
