本文共 1102 字，大约阅读时间需要 3 分钟。

链接：

大意：

根据二叉树的中序遍历in和后序遍历post构建二叉树。例子：

思路：

和前一题一样： 只不过是后序遍历序列的最后一个元素才是当前树的根节点值

另：使用前一题改进后的思路

代码：

/** * 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[] in, int[] post) {        if (in.length == 0)            return null;        Map
   
     map = new HashMap<>();        for (int i = 0; i < in.length; i++) {            map.put(in[i], i);        }        TreeNode root = buildTree(in, 0, in.length - 1, post, 0, post.length - 1, map);        return root;    }    public TreeNode buildTree(int[] in, int s1, int e1, int[] post, int s2, int e2, Map
    
      map) {        if (s1 > e1)            return null;        TreeNode root = new TreeNode(post[e2]); // 后序遍历的最后一个节点为根节点        int s = map.get(post[e2]), count = s - s1;        root.left = buildTree(in, s1, s - 1, post, s2, s2 + count - 1, map);        root.right = buildTree(in, s + 1, e1, post, s2 + count, e2 - 1, map);        return root;    }}
    
   

结果：

结论：

递归（算法）很美妙 ，有好的数据结构更美妙。

转载地址：http://etesi.baihongyu.com/