首页 > 试题广场 >

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

[编程题]在二叉树中找到累加和为指定值的最长路径长度
  • 热度指数：1645 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一颗二叉树和一个整数 sum，求累加和为 sum 的最长路径长度。路径是指从某个节点往下，每次最多选择一个孩子节点或者不选所形成的节点链。

输入描述:
第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行四个整数 fa，lch，rch，val，表示 fa 的左儿子为 lch，右儿子为 rch。val 表示 fa 节点的值(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)


输出描述:
输出一个整数表示最长链的长度。
示例1

输入

9 1
1 2 3 -3
2 4 5 3
4 0 0 1
5 8 9 0
8 0 0 1
9 0 0 6
3 6 7 -9
6 0 0 2
7 0 0 1
6

输出

4
示例2

输入

9 1
1 2 3 -3
2 4 5 3
4 0 0 1
5 8 9 0
8 0 0 1
9 0 0 6
3 6 7 -9
6 0 0 2
7 0 0 1
-9

输出

1

备注:


算法知识视频讲解
添加回答
C++
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
#include <iostream>
#include <unordered_map>

using namespace std;

typedef struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode* _left, TreeNode* _right) : val(x), left(_left), right(_right) {}
  ~TreeNode() {}
} *BT;

typedef int Id;

typedef struct TreeNodeInfo {
  Id id;
  int val;
  Id l_child, r_child;
} *INFO;

BT CreateBT(INFO infos, Id root_id) {
  if (!root_id) return nullptr;
  BT t     = new TreeNode(infos[root_id].val);
  t->left  = CreateBT(infos, infos[root_id].l_child);
  t->right = CreateBT(infos, infos[root_id].r_child);
  return t;
}

void dfs(TreeNode* root, int depth, int sum, int target,
         unordered_map<int, int>& mp, int& ans) {
  
  if (!root) return;
  sum += root->val;
  if (mp.find(sum) == end(mp))
    mp[sum] = depth;
  
  if (mp.find(sum - target) != end(mp))
    ans = max(ans, depth - mp[sum - target]);
  
  dfs(root->left,  depth + 1, sum, target, mp, ans);
  dfs(root->right, depth + 1, sum, target, mp, ans);
  
  // backtracking
  if (mp.find(sum) != end(mp) && mp[sum] == depth)
    mp.erase(sum); 
}

int main(const int argc, const char** argv) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int n, root_id;
  cin >> n >> root_id;
  
  TreeNodeInfo infos[n + 1];
  Id fa, l_ch, r_ch;
  int val;
  while (n--) {
    cin >> fa >> l_ch >> r_ch >> val;
    infos[fa].id      = fa;
    infos[fa].val     = val;
    infos[fa].l_child = l_ch;
    infos[fa].r_child = r_ch;
  }
  
  int target;
  cin >> target;
  
  BT t = CreateBT(infos, root_id);
  
  int ans = 0;
  unordered_map<int, int> mp{{0, 0}};
  dfs(t, 1, 0, target, mp, ans);
  
  cout << ans;
  return 0;
}

发表于 2021-08-03 21:12:51 回复(0)
牛客79631828号头像 牛客79631828号 
class Node {
    public int val;
    public Node right;
    public Node left;
    public Node (int val) {
        this.val = val;
    }
    public Node () {
    }
}

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node head = constructTree(sc, n);
        int k = sc.nextInt();
        int result = countLongest(head, k);
        System.out.println(result);
    }
    
    public static Node constructTree (Scanner sc, int n) {
        HashMap<Integer, Node> map = new HashMap<>();
        int rootID = sc.nextInt();
        Node root = new Node();
        map.put(rootID, root);
        for (int i = 0; i < n; i++) {
            int nodeID = sc.nextInt();
            int leftID = sc.nextInt();
            int rightID = sc.nextInt();
            int value = sc.nextInt();
            if (map.containsKey(nodeID)) {
                Node tmpNode = map.get(nodeID);
                tmpNode.val = value;
                Node leftNode = leftID == 0 ? null : new Node();
                Node rightNode = rightID == 0 ? null : new Node();
                tmpNode.left = leftNode;
                tmpNode.right = rightNode;
                if (leftID != 0)
                    map.put(leftID, leftNode);
                if (rightID != 0)
                    map.put(rightID, rightNode);
            }
        }
        return root;
    }
    
    public static int countLongest (Node head, int k) {
        //key表示某个累加和，value表示这个累加和在路径中最早出现层数
        HashMap<Integer, Integer> map = new HashMap<>();
        //表示不用包括任何节点就可以得到累加和为0
        map.put(0,0);
        return preOrder (head, k, map, 0, 1, 0);
    }
    
    public static int preOrder (Node head, int k, HashMap<Integer, Integer> map, int preSum, int level, int maxLen) {
        if (head == null) {
            return maxLen;
        }
        int curSum = preSum + head.val;
        if (!map.containsKey(curSum))
            map.put(curSum, level);
        if (map.containsKey(curSum-k)) {
            maxLen = Math.max(maxLen, level - map.get(curSum-k));
        }
        maxLen = preOrder(head.left, k, map, curSum, level + 1, maxLen);
        maxLen = preOrder(head.right, k, map, curSum, level + 1, maxLen);
        //跑到头来说明已经把一条能检测的路走到头了，此时该走另外一条路了，若不删除当前
        //新加进map里去的curSum和level，万一下一条路径有某个curSum-k恰好等于当前curSum
        //会误以为他们在同一条路径上，造成结果有误
        if (level == map.get(curSum))
            map.remove(curSum);
        return maxLen;
    }
}

发表于 2021-06-13 16:52:22 回复(0)
Java
小星教授头像 小星教授 
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;


public class Main {
	static int maxLen = 0;
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		TreeNode root = createTree(scanner, n);
		int sum = scanner.nextInt();
		Map<Integer, Integer> map = new HashMap<>();
		map.put(0, 0);
		maxLength(root,sum,map,0,1);
		System.out.print(maxLen);
	}
	
	
	
	private static void maxLength(TreeNode node, int sum, Map<Integer, Integer> map, int preSum, int level) {
		if(node==null) return;
		int currSum = preSum + node.value;
		if(!map.containsKey(currSum)) {
			map.put(currSum, level);
		}
		if(map.containsKey(currSum-sum)) {
			maxLen = Math.max(maxLen, level - map.get(currSum-sum));
		}
		maxLength(node.left,sum,map,currSum,level+1);
		maxLength(node.right,sum,map,currSum,level+1);
		if(map.get(currSum) == level) {
			map.remove(currSum);
		}
	}



	public static TreeNode createTree(Scanner scanner,int n) {
		Map<Integer, TreeNode> map = new HashMap<Integer, TreeNode>();
		int val = scanner.nextInt();
		TreeNode root = new TreeNode();
		map.put(val, root);
		for(int i=0;i<n;i++) {
			int father = scanner.nextInt();
			TreeNode node = map.get(father);
			
			int leftId = scanner.nextInt();
			if(leftId!=0) {
				TreeNode  left = new TreeNode();
				map.put(leftId,left );
				node.left = left;
			}
			
			int rightId = scanner.nextInt();
			if(rightId != 0) {
				TreeNode right = new TreeNode();
				map.put(rightId, right);
				node.right = right;
			}
			
			int value = scanner.nextInt();
			node.value = value;
			
		}
		return root;
	}
}


class TreeNode{
	int value;
	TreeNode left;
	TreeNode right;
	public TreeNode(int value, TreeNode left, TreeNode right) {
		super();
		this.value = value;
		this.left = left;
		this.right = right;
	}
	public TreeNode(int value) {
		super();
		this.value = value;
		this.left = null;
		this.right = null;
	}
	public TreeNode() {
	}
	
}

发表于 2019-10-29 12:06:43 回复(0)
Frankiet头像 Frankiet 
import java.util.HashMap;
import java.util.Scanner;

public class Main {

    static int max_length = 0;
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String [] first = in.nextLine().split(" ");
        int n = Integer.parseInt(first[0]);
        int root = Integer.parseInt(first[1]);
        int [][] nodes = new int[n][4];
        for(int i = 0;i < n;i ++){
            String [] str = in.nextLine().split(" ");
            int row = Integer.parseInt(str[0]);
            for(int j = 0;j < 4;j++){
                nodes[row-1][j] = Integer.parseInt(str[j]);  //使用数组来存放节点，每行第一个数-1确定节点所在的行。该行第一个元素代表根节点，第二个元素是其左子树，第三个元素是右子树，第四个是val
            }
        }
        int target = Integer.parseInt(in.nextLine());
        HashMap<Integer, Integer> map = new HashMap<>();  //key代表出现过的累加和，value代表这个累加和上次在哪一层出现的
        map.put(0, 0);   //一定要有，代表累加和为0的最早在0层就出现
        maxLength(nodes, root, target, map, 0,1);
        System.out.println(max_length);
    }
    
    public static void maxLength(int[][] nodes, int root, int target, HashMap<Integer, Integer> map, int preSum, int level){
        if(root == 0)
            return;
        int curSum = preSum + nodes[root-1][3];
                //当之前还没有出现过累加和为curSum的时候，加入map
        if(!map.containsKey(curSum)){
            map.put(curSum, level);
        }
    //比如说level为5时，curSum = 13,target = 5，那么就要看之前有没有和为8的出现
    //发现了level为2时，累加和为8
    //那么这里的max_length就可以试着更新为5-2 = 3.
    //之所以这么说，是因为有个关系一直存在，target = curSum - preSum.这是我们追求的
    //我们往map里加的都是preSum,所以就找curSum - target，使得追求的东西被实现
        if(map.containsKey(curSum - target)){
            max_length = Math.max(max_length, level - map.get(curSum - target));
        }
        //继续查找左右子树
        maxLength(nodes, nodes[root-1][1], target, map, curSum, level+1);
        maxLength(nodes, nodes[root-1][2], target, map, curSum, level+1);
//我们在map中存放的是上层所有的和，以及他们对应的level，
// 而如果在map中发现了curSum，且它的level不是上层，而且是当前这一层，那么说明curSum这个累加和的记录是在遍历到cur的时候加上去的
//那么就需要将这个记录删除掉，免得后面使用它。因为它并不是代表的上层的多少个数的和值。
      
        if(map.get(curSum) == level)
            map.remove(curSum);
    }
}//class end

编辑于 2020-03-19 14:08:14 回复(10)
Java
牛客329800565号头像 牛客329800565号
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Queue;
import java.util.LinkedList;
 
class TreeNode {
    public int value;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int value) {
        this.value = value;
    }
}
 
public class Main {
    private static HashMap<TreeNode,TreeNode> map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 构建二叉树
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        TreeNode root = new TreeNode(Integer.parseInt(params[1]));
        HashMap<Integer, TreeNode> map = new HashMap<Integer, TreeNode>();
        map.put(root.value,root);
        for(int i = 0; i < n; i++){
            params = br.readLine().split(" ");
            int fatherID= Integer.parseInt(params[0]);
            int leftID= Integer.parseInt(params[1]);
            int rightID= Integer.parseInt(params[2]);
            int fVal = Integer.parseInt(params[3]);
            TreeNode node = map.get(fatherID);
            node.value=fVal;
            if(leftID != 0) {
                node.left = new TreeNode(leftID);
                map.put(leftID, node.left);
            }
            if(rightID != 0) {
                node.right = new TreeNode(rightID);
                map.put(rightID, node.right);
            }
        }
        // 获得最近公共祖先
        String[] para = br.readLine().split(" ");
        int sum = Integer.parseInt(para[0]);
        System.out.println(getmaxlength(root,sum));
    }
    
 
    private static int getmaxlength(TreeNode head,int sum) {
        HashMap<Integer,Integer> summap=new HashMap<Integer,Integer>();
        summap.put(0,0);
        return preorder(head,sum,0,1,0,summap);
    }
    
    private static int preorder(TreeNode head, int sum,int presum,int level,int maxlen,HashMap<Integer,Integer> summap) {
        if(head==null) return maxlen;
        int cursum=presum+head.value;
        if(!summap.containsKey(cursum)){
            summap.put(cursum,level);
        }
        if(summap.containsKey(cursum-sum)){
            maxlen=Math.max(maxlen,(level-summap.get(cursum-sum)));
        }
        maxlen=preorder(head.left,sum,cursum,level+1,maxlen,summap);
        maxlen=preorder(head.right,sum,cursum,level+1,maxlen,summap);
        if(level==summap.get(cursum)){
            summap.remove(cursum);
        }
        return maxlen;
    }
    
    
}
发表于 2022-04-15 18:55:34 回复(0)
;roxrypmh头像 ;roxrypmh
参考(翻译)大佬的C++代码，6次里有一次没超时。真的不会初始化。 
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = 0
        self.right = 0
class Solution:
    def __init__(self):
        self.mmax = 99999
        self.v=[]
        self.mmaxdepth = 0
        
    def dfs(self, root, depth, sum):#C++用引用传递，不知如何实现。
        if root==0:
            return None
        sum = sum+self.v[root].val
        if sum==self.mmax and depth>self.mmaxdepth:
            self.mmaxdepth = depth
        self.dfs(self.v[root].left, depth+1, sum)
        self.dfs(self.v[root].right, depth+1, sum)
        
    def maxlen(self, root):
        if root==0:
            return 0
        maxdepth = 0
        self.dfs(root, 1,0)
        self.maxlen(self.v[root].left)
        self.maxlen(self.v[root].right)
        
    def ans(self):
        [n,root] = list(map(int,input().split()))
        self.v = [TreeNode(0) for i in range(n+1)]
        for i in range(n):
            [n1, l, r, val]=list(map(int,input().split()))            
            self.v[n1].left=l
            self.v[n1].right=r
            self.v[n1].val = val
        self.mmax = int(input())
        self.maxlen(root)
        print(self.mmaxdepth)

if __name__=="__main__":
    Solution().ans()


发表于 2021-08-08 19:59:39 回复(0)
Relili头像 Relili
看错了，一直不出来，无语了 
let [n,root]=readline().split(' ').map(item=>parseInt(item))
let myMap=new Map()

while(n--){
    let [fa,lch,rch,val]=readline().split(' ').map(item=>parseInt(item))
    myMap.set(fa,[lch,rch,val])
}
let len=parseInt(readline())


const listNode=function(val){
    this.val=val
    this.left=null
    this.right=null
}

const createTree=function(root){
    if(root){
        let [lch,rch,val]=myMap.get(root)
        let node=new listNode(val)
        node.left=createTree(lch)
        node.right=createTree(rch)
        return node
    }
}

const treeHead=createTree(root)

let res=0


const getMaxLength=function(treeHead,n){
    let sumMap=new Map()
    sumMap.set(0,0)
     preOrder(treeHead,n,0,1,sumMap)
}

const preOrder=function(root,target,presum,level,sumMap){
     if(root==null) return ;
      let curSum=presum+root.val
      
    if(!sumMap.has(curSum))
    sumMap.set(curSum,level)

  
    if(sumMap.has(curSum-target))
    res=Math.max(level-sumMap.get(curSum-target),res)
    
    preOrder(root.left,target,curSum,level+1,sumMap)
    preOrder(root.right,target,curSum,level+1,sumMap)

    if(sumMap.get(curSum)==level) sumMap.delete(curSum)

}

getMaxLength(treeHead,len)

console.log(res)


发表于 2021-07-13 16:29:51 回复(0)
包子冲汤胡辣汤头像 包子冲汤胡辣汤 
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n,root,mmax;
struct node{
    int data;
    int lchild,rchild;
};
vector<node> v;
void dfs(int root,int depth,int sum,int &mmaxdepth){
    if(root==0)
        return;
    sum=sum+v[root].data;
    if(sum==mmax&&depth>mmaxdepth)
    {
        mmaxdepth=depth;
    }
    dfs(v[root].lchild,depth+1,sum,mmaxdepth);
    dfs(v[root].rchild,depth+1,sum,mmaxdepth);
}
int maxlen(int root){
    if(root==0){
        return 0;
    }
    int m0=0,ml=0,mr=0;
    dfs(root,1,0,m0);
    ml=maxlen(v[root].lchild);
    mr=maxlen(v[root].rchild);
    return max(m0,max(ml,mr));
}
int main(){
    int n1,l,r,val;
    scanf("%d %d",&n,&root);
    v.resize(n+1);
    for(int i=0;i<n;++i){
        scanf("%d %d %d %d",&n1,&l,&r,&val);
        v[n1].data=val;
        v[n1].lchild=l;
        v[n1].rchild=r;
    }
    scanf("%d",&mmax);
    int sum=maxlen(root);
    printf("%d",sum);
}

编辑于 2020-04-05 15:55:09 回复(1)
皮蛋秀柚秋头像 皮蛋秀柚秋 
#include<bits/stdc++.h>
using namespace std;
// 双递归常规操作
// 此递归用于求解最长路径
void findLongestPath(int root,int* lc,int* rc,int* score,int rest,int cur_len,int& ans)
{
    // 累加和为0 更新最长路径长度
    if(rest==0)
        ans = max(ans,cur_len);
    // 到叶节点了 返回
    if(!root) return;

    // 累加上当前结点的值，继续去左右子树搜索
    findLongestPath(lc[root],lc,rc,score,rest-score[root],cur_len+1,ans);
    findLongestPath(rc[root],lc,rc,score,rest-score[root],cur_len+1,ans);

}
// 此递归用于遍历整棵树
// 因为最长路径可能以任意结点为起点
void visit(int root,int* lc,int* rc,int* score,int rest,int& ans)
{
    if(!root) return;
    findLongestPath(root,lc,rc,score,rest,0,ans);
    visit(lc[root],lc,rc,score,rest,ans);
    visit(rc[root],lc,rc,score,rest,ans);
}
int main()
{
    int n,root;
    cin>>n>>root;
    int* lc = new int[n+1];
    int* rc = new int[n+1];
    int* score = new int[n+1];
    int p;
    for(int i=0;i<n;++i)
    {
        cin>>p;
        cin>>lc[p]>>rc[p]>>score[p];
    }
    int target;
    cin>>target;
    int ans = 0;
    visit(root,lc,rc,score,target,ans);
    cout<<ans<<endl;

    return 0;
}
发表于 2020-02-04 16:51:26 回复(0)
提交观点

问题信息

模拟 树
上传者：小小
难度：
9条回答 5115浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号