从前序与中序遍历序列构造二叉树 递归

题目:

  从前序与中序遍历序列构造二叉树  递归

 

 思路:

  根据前序遍历的第一个数我们可以知道 根节点

  根据 根节点 去中序遍历中可以分出左树 与 右树

 

  运用极限逼近的思想,假设只有三个数据   

  前序【3,9,20】

  中序【9,3,20】

  去设计算法:   我们将中序中的数据存入map 中 value 存值得下标,根据蓝色字的思想,递归去构建树


 

(一)代码  递归

   

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        //map 中key 存中序遍历的元素, value 存元素下标
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i= 0 ; i < inorder.length ; i++){
            map.put(inorder[i],i);
        }

        return buildTreeNode(preorder,0,preorder.length,inorder,0,inorder.length,map);

    }

    public TreeNode buildTreeNode(int[] preorder,int pre_start,int pre_end,int[] inorder,int in_start,int in_end,Map<Integer, Integer> map){

        //当pre_Start == pre_End 递归出口
        if(pre_start == pre_end){
            return null;
        }

        //构建树
        TreeNode tree = new TreeNode(preorder[pre_start]);

        //获取中序遍历中root的位置
        int midkey = map.get(preorder[pre_start]);

        //根据中序遍历找到左边的数量 ,  通过这个去算先序遍历的结束位置
        int leftnum = midkey - in_start;

        tree.left = buildTreeNode(preorder,pre_start+1,pre_start+1+leftnum,inorder,in_start,midkey-1,map);
        tree.right = buildTreeNode(preorder,pre_start+1+leftnum,pre_end,inorder,midkey+1,in_end,map);

        return tree;
    }
}

 

 

 

      利好白酒

  

 

上一篇:105. 从前序与中序遍历序列构造二叉树


下一篇:【django入门】 14 网页关联MySQL“多”字段表(增)