[数据结构与算法]数据结构—数组构造完全二叉树

构造完全二叉树

    public static TreeNode createTree(int index,int[] arr){
        if(index>=arr.length){
            return null;
        }
        TreeNode root = new TreeNode();
        root.val = arr[index];
        root.left = createTree(index*2+1,arr);
        root.right = createTree(index*2+2,arr);
        return root;
    }
    static class TreeNode{
        public TreeNode left;
        public TreeNode right;
        public Integer  val;
        public TreeNode(){

        }
    }

后序遍历下

    public static void afterOrder(TreeNode root){
        TreeNode prev = null;
        Stack<TreeNode> s = new Stack<>();
        while(root!=null || !s.empty()){
            while (root!=null){
                s.add(root);
                root = root.left;
            }
            root = s.pop();
            if(root.right==null || root.right==prev){
                System.out.print(root.val+" ");
                prev = root;
                root = null;
            }else{
                s.add(root);
                root = root.right;
            }
        }
    }

调用创建二叉树方法

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,4,5,6};
        TreeNode tree = createTree(0, arr);
        afterOrder(tree);

    }

打印

4 5 2 6 3 1