LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal 由前序和中序遍歷建立二叉樹 C++...

LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal 由前序和中序遍歷建立二叉樹 C++

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

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

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3/ \9  20/  \15   7

前序、中序遍歷得到二叉樹，可以知道每一次前序新數組的第一個數為其根節點。在中序遍歷中找到根節點對應下標，根結點左邊為其左子樹，根節點右邊為其右子樹，再根據中序數組中的左右子樹個數，找到對應的前序數組中的左右子樹新數組。設每次在中序數組中對應的位置為i，則對應的新數組為：

前序新數組：左子樹[pleft+1,pleft+i-ileft],右子樹[pleft+i-ileft+1,pright]

中序新數組：左子樹[ileft,i-1],右子樹[i+1,iright]? C++

 1 TreeNode* buildTree(vector<int>& preorder,int pleft,int pright,vector<int>& inorder,int ileft,int iright){
 2         if(pleft>pright||ileft>iright)
 3             return NULL;
 4         int i=0;
 5         for(i=ileft;i<=iright;i++){
 6             if(preorder[pleft]==inorder[i])
 7                 break;
 8         }
 9         TreeNode* cur=new TreeNode(preorder[pleft]);
10         cur->left=buildTree(preorder,pleft+1,pleft+i-ileft,inorder,ileft,i-1);
11         cur->right=buildTree(preorder,pleft+i-ileft+1,pright,inorder,i+1,iright);
12         return cur;
13     }
14     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
15         return buildTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
16     }

posted on 2019-04-17 14:48?木落長安rr 閱讀(...) 評論(...) 編輯收藏

轉載于:https://www.cnblogs.com/hhhhan1025/p/10723478.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/386995.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/386995.shtml
英文地址，請注明出處：http://en.pswp.cn/news/386995.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！