剑指offer_根据前序和中序确定二叉树

ゞ浴缸里的玫瑰 2022-06-14 00:48 77阅读 0赞

/*
    重建二叉树：
    根据前序和中序确定二叉树
    思路：
    递归，找到前序的第一个元素在中序中的位置，该位置之前的元素均为左子树，该位置之后的元素均为右子树，递归处理左右子树
    */
    class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
     }
     
    public class ReConstructBinaryTree {
        public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
            
    		//判断序列是否为空
    		if (pre==null||in==null)
            {
    			return null;
            }
    
    		return construct(pre, 0, pre.length-1, in, 0, in.length-1);
    	}
    
    		public static TreeNode construct(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd){
    			
    			//创建根节点
    			int rootVal=pre[preStart];
    			TreeNode tn=new TreeNode(rootVal);
    			tn.left=null;
    			tn.right=null;
    
    			//找到跟结点在中序序列中的位置
    			int inRootLoc=-1;
    			for (int i=0;i<in.length;i++ )
    			{
    				if (in[i]==rootVal)
    				{
    					inRootLoc=i;
    					break;
    				}
    			}
    			if (inRootLoc==-1)
    			{
    				System.out.println("非法输入");
    				return null;
    			}
    
    			//左子树元素个数
    			int leftLength=inRootLoc-inStart;
    
    			//左子树前序序列
    			int preStart_left=preStart+1;
    			int preEnd_left=preStart+leftLength;
    
    			//右子树前序序列
    			int preStart_right=preEnd_left+1;
    			int preEnd_right=preEnd;
    			
    			//左子树中序序列
    			int inStart_left=inStart;
    			int inEnd_left=inRootLoc-1;
    
    			//右子树中序序列
    			int inStart_right=inRootLoc+1;
    			int inEnd_right=inEnd;
    
    			if (leftLength>0)
    			{
    				tn.left=construct(pre, preStart_left, preEnd_left, in, inStart_left, inEnd_left);
    			}
    			if (leftLength<preEnd-preStart)
    			{
    				tn.right=construct(pre, preStart_right, preEnd_right, in, inStart_right, inEnd_right);
    			}
    
    			return tn;
    		}
    
    		public static void print(TreeNode tn)
    		{
    			if (tn!=null)
    			{
    				System.out.println(tn.val);
    				print(tn.left);
    				print(tn.right);
    			}
    		}
    
    		public static void main(String[] args)
    		{
    			int[] pre={1,2,4,7,3,5,6,8};
    			int[] in={4,7,2,1,5,3,8,6};
    			
    			TreeNode tn=reConstructBinaryTree(pre,in);
    			
    			print(tn);
    
    		}
    }