2013年09月09日

二叉树中查找和最大的节点集合


有这样一个题目,描述如下:

给定一个二叉树,每个节点具备一个权重值,按照如下规则选取二叉树中的节点,如果选取了某个节点,那么其子节点都不能被选取了。在这个规则下面,如何保证选取的和最大。

分析

关于二叉树有一些系列的基本问题:

这一类问题基本上都可以利用二叉树的递归遍历方式来处理,根据题目要求的不同,可能采取先序,后序或者中序遍历等等。其中最大的不同也就是递归过程中的某些处理。往往感到棘手的也就是如何写这个递归过程,总有一种似是而非的感觉。其实当想清除一个问题之后,处理递归来就顺手很多,在回溯过程中,已经得到子问题的最优解,再思考如何将这个子问题的最优解和当前的节点比较或处理就可以。典型的是将二叉树改为双向链表,使用一个指针pre记住前一个节点,那么在某次回溯的过程中,意味着前面的节点已经构成双向链表了,如何处理好现在的节点与pre的关系就ok了。因为每次递归调用都是同样的代码。

对于这个问题,类似于动态规划,从根节点出发,找到其左子树和右子树的最优解,判断其和是否大于根节点的权重,若是的,则根节点放弃。依次递归,判断每个节点的左右子树的最大值与该节点的值的大小关系。很显然,我们如果从叶子节点往上走,就可以在一次遍历过程中,完成全部的工作。

代码

基于上面的分析,写出下面的代码,还包括回溯打印选中的节点的过程。整个递归的代码很简洁,不超过十行。

#include<iostream>
#include<vector>
#include<iterator>


using namespace std;

typedef struct tree{
    int value;
    struct tree *left;
    struct tree *right;
    tree(int val, tree* l, tree* r){
        value = val;
        left = l;
        right = r;
    }
}BinaryTree;

void inorder(BinaryTree *root){
    if(root == NULL)
        return;
    inorder(root->left);
    cout << root->value << " ";
    inorder(root->right);
}

void partytime(BinaryTree *root,int *weight){
    if(root == NULL)
        return;
    int left = 0, right = 0;  
    partytime(root->left,&left); 
    partytime(root->right,&right); 

    if(left + right > root->value){
        *weight = left + right;
    }else{
        *weight = root->value;    
    }
}

void partytime(BinaryTree *root,int *weight,vector<int>& vec){
    if(root == NULL)
        return;
    int left = 0, right = 0;  
    partytime(root->left,&left,vec); 
    partytime(root->right,&right,vec); 

    if(left + right > root->value){
        *weight = left+right;
    }else
        *weight = root->value;    
    vec.push_back(*weight);
}

void tracingback(BinaryTree *node,vector<int>& vec,int index){
    if(node == NULL || vec.size() <= index)
        return;
    if(node->value == vec.at(index)){
        cout << node->value << " ";
        return;
    }
    int i = 0;
    for(i; i < index; i++){
        if(vec[i] == vec.at(index)-vec.at(index-1))
            break;
    }
    tracingback(node->left,vec,i);     
    tracingback(node->right,vec,index-1);     
}

int main(){
    BinaryTree one(4,NULL,NULL);
    BinaryTree tmp(5,NULL,NULL);
    BinaryTree two(3,&one,&tmp);
    BinaryTree thr(2,NULL,NULL);
    BinaryTree fou(12,&thr,&two);
    BinaryTree fiv(3,NULL,NULL);
    BinaryTree six(6,NULL,&fiv);
    BinaryTree sev(2,NULL,NULL);
    BinaryTree egi(5,&six,&sev);
    BinaryTree root(10,&fou,&egi);

    inorder(&root);
    cout << endl;
    int weight = 0;
    vector<int> vec;
    partytime(&root,&weight);
    partytime(&root,&weight,vec);
    copy(vec.begin(),vec.end(),ostream_iterator<int,char>(cout," "));
    cout << endl;
    cout << "tracing back: ";
    tracingback(&root,vec,vec.size()-1);
    cout << endl;
    
    return 0;
}

总结

写递归的代码,切记需要把递归的过程想清楚,这样若需要将递归转换到循环来处理时,会更加顺手。

前一篇: Linux逻辑卷的学习 后一篇: Openstack文章汇总