本文主要是介绍Leetcode106.从中序与后序遍历序列构造二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
看到二叉树的遍历就首先想到递归。
-
第一步：如果数组大小为零的话，说明是空节点了。
-
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
-
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
-
第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
-
第五步：切割后序数组，切成后序左数组和后序右数组
-
第六步：递归处理左区间和右区间
class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if(inorder.length==0 || postorder.length==0) return null;return traversal(inorder,postorder);}public TreeNode traversal(int[] inorder,int[] postorder){if(postorder.length==0) return null;TreeNode root=new TreeNode(postorder[postorder.length-1]);if(postorder.length==1) return root;int index;for(index=0;index<inorder.length;index++){if(inorder[index]==postorder[postorder.length-1]) break;}int[] leftInorder=Arrays.copyOfRange(inorder,0,index);int[] rightInorder=Arrays.copyOfRange(inorder,index+1,inorder.length);int[] leftPostorder=Arrays.copyOfRange(postorder,0,leftInorder.length);int[] rightPostorder=Arrays.copyOfRange(postorder,leftInorder.length,postorder.length-1);root.left=traversal(leftInorder,leftPostorder);root.right=traversal(rightInorder,rightPostorder);return root;} }
这篇关于Leetcode106.从中序与后序遍历序列构造二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
