6 8 tree_uva58 - nuaazdh/acm GitHub Wiki

##例题6-7 树(Tree UVa457) ###问题

给定一个带权值的二叉树，找出一个叶子结点，使得从根节点到该结点路径上的所有结点的权值之和最小。如果存在多个这样的结点，要求结点本身的值最小。 二叉树的以中序遍历 和 后序遍历顺序给定。

样例输入

3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255

样例输出

1
3
255

###分析 首先可以根据中序遍历和先序遍历的结果，建立起二叉树。然后找到每个叶子结点的路径权值，从根节点出发，当前结点的权值等于父节点权值与自身权值之和。

###code in C++

#include <iostream>
#include <vector>
#include <sstream>

const int max_size = 10100;

int inorder[max_size];
int postorder[max_size];
int min_path, min_node;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) { }
};

TreeNode *build_tree(int in_beg, int in_end, int post_beg, int pos_end) {
    if (in_end < in_beg || pos_end < post_beg || (pos_end - post_beg != in_end - in_beg))
        return NULL;
    TreeNode *root = new TreeNode(postorder[pos_end]);
    int root_pos = in_beg;
    while (inorder[root_pos] != postorder[pos_end] && root_pos <= in_end) ++root_pos;
    if (root_pos > in_end)
        return root;
    root->left = build_tree(in_beg, root_pos - 1, post_beg, post_beg + (root_pos - in_beg) - 1);
    root->right = build_tree(root_pos + 1, in_end, pos_end - (in_end - root_pos), pos_end - 1);
    return root;
}

void find_min_path(TreeNode *root, int parent) {
    if (!root)
        return;
    if (!(root->left || root->right)) {
        if (min_node == 0) {
            min_node = root->val;
        }
        if (parent + root->val < min_path) {
            min_path = parent + root->val;
            min_node = root->val;
        } else if (parent + root->val == min_path && min_node > root->val) {
            min_node = root->val;
        }
    }
    find_min_path(root->left, parent + root->val);
    find_min_path(root->right, parent + root->val);
}

void free_root(TreeNode *root) {
    if (!root)
        return;
    if (!(root->left || root->right)) {
        delete root;
        root = NULL;
    }
    if(root->left) free_root(root->left);
    if(root->right) free_root(root->right);
    delete root;
    root = NULL;
}

int main() {
    std::string line;
    while (std::getline(std::cin, line)) {
        min_path = 0, min_node = 0;
        std::stringstream ss(line);
        int i = 0;
        while (ss >> inorder[i]) { min_path += inorder[i], ++i; }
        std::getline(std::cin, line);
        std::stringstream ss2(line);
        i = 0;
        while (ss2 >> postorder[i]) ++i;
        TreeNode *root = build_tree(0, i - 1, 0, i - 1);
        find_min_path(root, 0);
        std::cout << min_node << std::endl;
        free_root(root);
    }
}

###点评 一个比较直观的实现，主要注意几点：

  1. 递归建立二叉树时，对越界判断；
  2. 注意审题，一个结点的路径权值和，需要加上自身结点的值；
⚠️ **GitHub.com Fallback** ⚠️