程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:Construct Binary Tree from Preorder and Inorder Traversal

leetcode筆記:Construct Binary Tree from Preorder and Inorder Traversal

編輯:C++入門知識

leetcode筆記:Construct Binary Tree from Preorder and Inorder Traversal


一. 題目描述

Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.

二. 題目分析

這道題考察了先序和中序遍歷,先序是先訪問根節點,然後訪問左子樹,最後訪問右子樹;中序遍歷是先遍歷左子樹,然後訪問根節點,最後訪問右子樹。

做法都是先根據先序遍歷的概念,找到先序遍歷的第一個值,即為根節點的值,然後根據根節點將中序遍歷的結果分成左子樹和右子樹,然後就可以遞歸的實現了。

按照上述做法,時間復雜度為O(n^2),空間復雜度為O(1)

三. 示例代碼

#include 
#include 
#include 

using namespace std;

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

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

class Solution
{
private:
    TreeNode* buildTree(vector::iterator PreBegin, vector::iterator PreEnd,
                        vector::iterator InBegin, vector::iterator InEnd)
    {
        if (PreBegin == PreEnd)
        {
            return NULL;
        }

        int HeadValue = *PreBegin;
        TreeNode *HeadNode = new TreeNode(HeadValue);

        vector::iterator LeftEnd = find(InBegin, InEnd, HeadValue);
        if (LeftEnd != InEnd)
        {
            HeadNode->left = buildTree(PreBegin + 1, PreBegin + (LeftEnd - InBegin) + 1,
                             InBegin, LeftEnd);
        }

        HeadNode->right = buildTree(PreBegin + (LeftEnd - InBegin) + 1, PreEnd,
                                LeftEnd + 1, InEnd);

        return HeadNode;
    }
public:
    TreeNode* buildTree(vector& preorder, vector& inorder)
    {
        if (preorder.empty())
        {
            return NULL;
        }

        return buildTree(preorder.begin(), preorder.end(), inorder.begin(),
                         inorder.end());

    }
};

四. 小結

該題考察了基礎概念,並不涉及過多的算法問題。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved