【剑指offer-Java版】06重建二叉树

比眉伴天荒 2022-08-21 08:53 149阅读 0赞

输入二叉树的前序和中序遍历，重建该二叉树

public class _Q06 {
    
        public BinaryTreeNode ConstractBinaryTree(int preOrder[], int inOrder[]) throws Exception{
            if(preOrder == null || inOrder == null) return null; // 处理非法输入
    
            if(preOrder.length == 0 || inOrder.length == 0) return null; // 边界条件 -- 和处理非法输入的作用是不同的-注意
            // 遇到的问题：一开始当做是C++里面的数组来处理，直接按是否等于空来确定，但是此处都是对象
            // 而且Arrays.copyOfRange要么返回一个对象要么抛异常
            // 所以通过是否为空来判断也是不合理的而且直接挂掉或者异常
            // if(preOrder == null || inOrder == null) return null;
    
            if(preOrder.length != inOrder.length) throw new Exception("order length is not same");
    
            boolean find = false;
    
            BinaryTreeNode root = new BinaryTreeNode();
    
            for(int i=0; i<inOrder.length; i++){
    
                if(inOrder[i] == preOrder[0]){
    
                    find = true;
    
                    root.value = preOrder[0];
                    root.leftChild = ConstractBinaryTree(Arrays.copyOfRange(preOrder, 1, i+1),
                            Arrays.copyOfRange(inOrder, 0, i));
    
                    root.rightChild = ConstractBinaryTree(Arrays.copyOfRange(preOrder, i+1, preOrder.length),
                            Arrays.copyOfRange(inOrder, i+1, inOrder.length));
    
                }
            }
    
            if (!find) {
                throw new Exception("invalid input");
            }
    
            return root;
        }
    
        // 中序输出
        public void PrintTree(BinaryTreeNode root){
            if(root == null) return;
    
            PrintTree(root.leftChild);
    
            System.out.print(root.value + " ");
    
            PrintTree(root.rightChild);
    
        }
    
        }

测试代码：

public class _Q06Test extends TestCase{
        
    
        _Q06 q06 = new _Q06();
        int pre[] = {
       1,2,4,7,3,5,6,8};
        int in[] = {
       4,7,2,1,5,3,8,6};
    
        /**
         * 
         * @comment testQ06首字母要小写，否则出现如下错误： no test found in ***
         * @param    
         * @return void  
         * @throws
         * @date 2016年4月13日 下午4:31:49
         */
        public void testQ06(){
            try {
    
                BinaryTreeNode root = q06.ConstractBinaryTree(pre, in);
    
                q06.PrintTree(root);
    
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        }

二叉树结点：

public class BinaryTreeNode<T>{
        public T value;
        public BinaryTreeNode leftChild;
        public BinaryTreeNode rightChild;
        }