[C#版剑指offer]根据前序遍历和后序遍历重建二叉树

谁践踏了优雅 2023-06-03 02:59 13阅读 0赞

前序遍历与后序遍历 重建二叉树的关键在于如何写好递归代码段中几个节点。

具体代码如下所示

public class TreeNode {
    
            public int data;
            TreeNode leftNode;
            TreeNode rightNode;
            public TreeNode(int data){
                this.data = data;
            }
        public  static TreeNode rebuildBinaryTree(int[] preorder,int[] inorder){
            if(preorder==null||inorder==null){
                return null;
            }
            TreeNode root=rebuildBinaryTreeCore(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
            return root;
        }
        public static TreeNode rebuildBinaryTreeCore(int[] preorder,int startpreorder,int endpreorder,int[] inorder,int startinorder,int endinorder){
            if(startpreorder>endpreorder||startinorder>endinorder){
                return null;
            }
            TreeNode root=new TreeNode(preorder[startpreorder]);
            for(int i=startinorder;i<=endinorder;i++){
                if(preorder[startpreorder]==inorder[i]){
                    root.leftNode = rebuildBinaryTreeCore(preorder,startpreorder+1,startpreorder+i-startinorder,inorder,startinorder,i-1);
                    root.rightNode = rebuildBinaryTreeCore(preorder,i-startinorder+startpreorder+1,endpreorder,inorder,i+1,endinorder);
                }
            }
            return root;
        }
        public static void printpostorder(TreeNode root){
            if(root ==null){
                return;
            }else{
                printpostorder(root.leftNode);
                printpostorder(root.rightNode);
                System.out.println(root.data);
            }
    
        }
    
        public static void main(String[] args) {
            int[] preorder = {3,9,20,15,7};
            int[] inorder =  {9,3,15,20,7};
    
            TreeNode node = rebuildBinaryTree(preorder,inorder);
            printpostorder(node);
    
        }
    }