有一个二叉树，节点全部为整数，如何找到一个子树，它所有节点

[问答题]

有一个二叉树，节点全部为整数，如何找到一个子树，它所有节点的和最大？要求编程序实现。

推荐

大漠苍鹰

使用递归方法，可以使用前序遍历，首先分别计算左右子树各自的子树和，然后记录目前最大的；

再加入当前的父节点，再计算父节点开头的子树是否最大；该层递归上去即可。

public class MaxSumSubTree {
class TreeNode{
TreeNode left,right;
int tag;
TreeNode(int tag){
this.tag = tag;
}
}

private TreeNode maxRoot = new TreeNode(0);
public int find(TreeNode root){
if(root==null){
return 0;
} else{
int lSum = find(root.left);
int rSum = find(root.right);
if(maxRoot.tag<lSum)
maxRoot = root.left;
if(maxRoot.tag<rSum)
maxRoot = root.right;
return root.tag+lSum+rSum;
}
}
}

编辑于 2015-01-27 21:35:30 回复(1)

KissGoodbye

public int findMax(Node root,Node maxNode,int max){
		if(root == null){
			return 0;
		}
		int leftMax = 0;
		int rightMax = 0;
		if(root.leftChild != null){
			leftMax = findMax(root.leftChild,root,max);
		}
		if(root.rightChild != null){
			rightMax = findMax(root.rightChild,root,max);
		}
		if(root.data+leftMax+rightMax > max){
			max = root.data + leftMax + rightMax;
			maxNode = root;
		}
		return max;
	}

发表于 2017-03-15 12:21:00 回复(0)

叫我大头

发表于 2017-12-27 22:28:38 回复(0)

像我这么吊的下水道还有六个

// 二叉树
typedef struct Tree_ 
{
	int data;
	int val;
	struct Tree_ * left;
	struct Tree_ * right;
} Tree;

// 找到二叉树的子树的节点和的最大值
int findSubTreeMaxSum(Tree *t, int *maxLen)
{
	if(NULL == t || NULL == maxLen)
	{
		return 0;
	}

	int leftVal = findSubTreeMaxSum(t->left, maxLen);
	int rightVal = findSubTreeMaxSum(t->right, maxLen);

	t->val = leftVal + rightVal + t->data;

	if(t->val > *maxLen)
	{
		*maxLen = t->val;
	}

	return t->val;
}

发表于 2015-07-30 11:25:57 回复(0)

若水/爆米花

#include <iostream>
#include <stdio.h>
#include <map>
#include <stdlib.h>
#include <queue>
#include <stack>
using namespace std;
typedef struct node
{
int data;
struct node *left;
struct node *right;
}BStree;
BStree* creat_tree()
{
   int a;
   BStree *T;
   printf("input the data:\n");
   std::cin>>a;
if(a==0) T = NULL;
   else
   {
     T = (BStree*)malloc(sizeof(BStree));
     T->data = a;
     T->left = creat_tree();
     T->right = creat_tree();
   }
   return T;
}
int maopao(int *a,int size)

{
int temp = 0;
bool flag = false;
for (int i = 1; i < size; ++i)
{
     for (int j = size-1; j>=i; --j)
     {
      if(a[j]<a[j-1])
      {
       temp = a[j];
       a[j] = a[j-1];
       a[j-1] = temp;
       flag = true;
      }
     }
     if(!flag) break;
}
return a[size-1];
}
void find_big_tree( BStree * T)
{
BStree *p;
std::vector<int> a;
map<int,BStree *> maa;
int i =0, m =0;
queue<BStree*> q;
q.push(T);
while(!q.empty())
{
    p = q.front();
    m += p->data;
    q.pop();
    if(p->left) {q.push(p->left); m+=p->left->data; }
    if(p->right) {q.push(p->right); m+=p->right->data;}
    if((p)&&((p->left)||(p->right)))
    {
      a.push_back(m) ;
      maa[a[i]] = p;
    }
    m = 0;
}
int temp = maopao(&a[0],a.size());
p = maa[temp];
cout<<p->data<<" "<<p->left->data<<"   "<<p->right->data<<"\n";

}
int main()
{
BStree *T;
T = creat_tree();
find_big_tree( T);
return 0;
}

发表于 2015-06-17 18:42:30 回复(1)

leef

typedef struct __node
{
int value ;
int child_tree_sum;
struct __node* lchild;
struct __node* rchild;
}node;

int child_tree_sum(node* root)
{
if( NULL == root )return 0;
root->child_tree_sum += root->lchild.value;
if( root->lchild )
{
root->child_tree_sum += child_tree_sum(root->lchild);
}
if( root->rchild )
{
root->child_tree_sum += child_tree_sum(root->rchild);
}
return root->child_tree_sum;
}

node* find_max_child_tree(node* root, node* p)
{

if( NULL == p )
p = root;
else if( p->child_tree_sum < root->child_tree_sum )
p = root;
if( root->lchild ) find_max_child_tree(root->lchild, p);
if( root->lchild ) find_max_child_tree(root->rchild, p);

return p;
}

发表于 2014-11-30 14:10:02 回复(0)