每天一道leetcode-106从中序与后序遍历序列构造二叉树
- 2019 年 10 月 4 日
- 筆記
昨天的题解
每天一道leetcode-106从中序与后序遍历序列构造二叉树
题目
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]
题目详解
思路
- 我们首先要得到从后序序列中获取根节点，然后遍历中序序列，找到根节点的位置，以此直到其左子树和右子树的范围。 当我得到其左子树之后，事情就开始重复了，我们仍然需要根据后序序列中找到这颗左子树的根节点，然后再根据中序序列得到这颗左子树根节点的左右子树,就这样一直重复这个过程，直到，左子树只有一个节点，那么也就是在递归的最深的那一层，这时候就把这个节点返回，然后就一层层回溯，这样就完成了左子树的构建
- 对于右子树也是同理。
- 和leetcode 105类似，稍微改改就AC
代码
/** * 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) { if(postorder == null || inorder == null || postorder.length==0){ return null; } return buildCore(postorder,0,postorder.length-1,inorder,0,inorder.length-1); } private TreeNode buildCore(int[] postorder,int postSt,int postEnd,int[] inorder,int inSt,int inEnd){ //后序遍历最后一个节点是根节点 int rootValue = postorder[postEnd]; TreeNode root = new TreeNode(rootValue); //后序序列只有根节点 if(postSt == postEnd){ return root; } //遍历中序序列，找到根节点的位置 int rootInorder = inSt; while(inorder[rootInorder]!=rootValue&&rootInorder<=inEnd){ rootInorder++; } //左子树的长度 int leftLength = rootInorder - inSt; //后序序列中左子树的最后一个节点 这里一个tips是自己举一个简单的例子去找这个关系式 int leftPostEnd = postSt + leftLength - 1; //左子树非空 左子树长度大于等于0 if(leftLength>0){ //重建左子树 root.left = buildCore(postorder,postSt,leftPostEnd,inorder,inSt,rootInorder - 1); } //右子树非空 postEnd 和postSt是前序数组的结尾和开头，相减就是长度，如果左子树长度小于整个长度 //那么说明右子树肯定 存在。那么对右子树也进行同样的构建树的操作。 if(leftLength < postEnd - postSt){ //重建右子树 root.right = buildCore(postorder,leftPostEnd +1,postEnd-1,inorder,rootInorder+1,inEnd); } return root; } }
代码截图（避免乱码）
