根據一棵樹的中序遍歷與后序遍歷構造二叉樹。注意: 你可以假設樹中沒有重復的元素。例如，給出中序遍歷 inorder = [9,3,15,20,7] 后序遍歷 postorder = [9,15,7,20,3] 返回如下的二叉樹：3/ \9 20/ \15 7

解題思路

根據后序遍歷的最后一個元素是父節點，在中序遍歷中查找父節點，父節點的左邊為左子樹中序遍歷的序列，右邊為右子樹中序遍歷的序列，根據左右子樹的長度，在后序遍歷中找出左右子樹的后序遍歷的序列，再遞歸下一層。

代碼

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/ class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {return buildT(inorder,0,inorder.length-1,postorder,0,postorder.length-1);}public TreeNode buildT(int[] inorder,int inl,int inr, int[] postorder,int pol,int por) {if(inl>inr||pol>por) return null; TreeNode treeNode=new TreeNode(postorder[por]);int temp=0;while (inorder[inl+temp]!=postorder[por]) temp++;treeNode.left=buildT(inorder, inl, inl+temp-1, postorder, pol, pol+temp-1);treeNode.right=buildT(inorder,inl+temp+1,inr,postorder,pol+temp,por-1);return treeNode;} }

總結

以上是生活随笔為你收集整理的leetcode106. 从中序与后序遍历序列构造二叉树（dfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。