频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
105. Construct Binary Tree from Preorder and Inorder Traversal“编程题”
2017-11-23 13:51:47         来源:SYSU_xiandan的博客  
收藏   我要投稿

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

由题意得,这题是给出一个二叉树的前序和中序序列,然后要求构造这样的一个二叉树。用递归的方法比较容易懂和好写,所以打算用递归写。例如给出一个前序序列是 1 2 4 5 3 6 7,中序序列为4 2 5 1 6 3 7。这个二叉树为:

观察两个序列,显然前序中的第一个就是根结点,观察中序,中序序列中的1是根节点,而前面部分是左子树,后面部分为右子树,所以递归的话,就可以这样划分成子问题来解决,代码如下:

Code(LeetCode运行16ms)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector& preorder, vector& inorder) {
        return buildTree(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }
    
    TreeNode* buildTree(vector::iterator pre_begin, vector::iterator pre_end, vector::iterator in_begin, vector::iterator in_end) {
        if (pre_begin == pre_end) {
            return NULL;
        }
        if (in_begin == in_end) {
            return NULL;
        }
        
        auto root = new TreeNode(*pre_begin);
        auto RootPos = find(in_begin, in_end, *pre_begin);
        auto leftSize = distance(in_begin, RootPos);
        
        root -> left = buildTree(next(pre_begin), next(pre_begin, leftSize + 1), in_begin, next(in_begin, leftSize));
        root -> right = buildTree(next(pre_begin, leftSize + 1), pre_end, next(RootPos), in_end);
        return root;
    }
};
点击复制链接 与好友分享!回本站首页
上一篇:项目3Dijkstra算法的验证的例程
下一篇:Eric6与pyqt5简单学习过程
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站