区块链技术博客
www.b2bchain.cn

前中后构造二叉树

这篇文章主要介绍了前中后构造二叉树,通过具体代码讲解8322并且分析了前中后构造二叉树的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了前中后构造二叉树。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/8322.html。具体如下:

106. 从中序与后序遍历序列构造二叉树 

 /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; }  * }  */ class Solution {   int post_idx;   int[] postorder;   int[] inorder;    HashMap<Integer, Integer> idx_map = new HashMap<Integer, Integer>();    public TreeNode helper(int in_left, int in_right) {     if (in_left > in_right)  return null;     TreeNode root = new TreeNode( postorder[post_idx]);     int index = idx_map.get(postorder[post_idx]);      post_idx--;     //先右面     root.right = helper(index + 1, in_right);     root.left = helper(in_left, index - 1);     return root;   }    public TreeNode buildTree(int[] inorder, int[] postorder) {     this.postorder = postorder;     this.inorder = inorder;     post_idx = postorder.length - 1;     for(int i=0;i<inorder.length;i++){            idx_map.put(inorder[i],i);     }     return helper(0, inorder.length - 1);   } }   

105. 从前序与中序遍历序列构造二叉树

 /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; }  * }  */ class Solution {     int[] pre;     int[] ino;     Map<Integer,Integer> inMap=new HashMap<>();     int preindex=0;     public TreeNode buildTree(int[] preorder, int[] inorder) {         pre=preorder;         ino=inorder;         for(int i=0;i<inorder.length;i++){              inMap.put(inorder[i],i);         }                  return helper(0,inorder.length-1);     }     private TreeNode helper(int inStart,int inEnd){          if(inStart>inEnd) return null;          TreeNode root=new TreeNode(pre[preindex]);          int mid=inMap.get(pre[preindex]);           preindex++;          root.left=helper(inStart,mid-1);          root.right=helper(mid+1,inEnd);          return root;     }  }

889. 根据前序和后序遍历构造二叉树 

 /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; }  * }  */ class Solution {     public TreeNode constructFromPrePost(int[] pre, int[] post) {         if(pre==null || pre.length==0) {             return null;         }         return dfs(pre,post);     } 	     private TreeNode dfs(int[] pre,int[] post) {         if(pre==null || pre.length==0) {             return null;         }         //数组长度为1时,直接返回即可         if(pre.length==1) {             return new TreeNode(pre[0]);         }         //根据前序数组的第一个元素,创建根节点          TreeNode root = new TreeNode(pre[0]);         int n = pre.length;         for(int i=0;i<post.length;++i) {             if(pre[1]==post[i]) {                 //根据前序数组第二个元素,确定后序数组左子树范围                 int left_count = i+1;                 //拆分前序和后序数组,分成四份                 int[] pre_left = Arrays.copyOfRange(pre,1,left_count+1);                 int[] pre_right = Arrays.copyOfRange(pre,left_count+1,n);                 int[] post_left = Arrays.copyOfRange(post,0,left_count);                 int[] post_right = Arrays.copyOfRange(post,left_count,n-1);                 //递归执行前序数组左边、后序数组左边                 root.left = dfs(pre_left,post_left);                 //递归执行前序数组右边、后序数组右边                 root.right = dfs(pre_right,post_right);                 break;             }         }         //返回根节点         return root;     } }	  

 

本文地址https://www.b2bchain.cn/8322.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 前中后构造二叉树
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们