由数组构造二叉树

image.png
image.png

思路

1.根节点下标为a,根的左子树下标为b,根的右子树下标为c:b=ax2,c=ax2+1
2.数组中每赋一个给TreeNode,则置0

代码

public static TreeNode buildTree(int[] array,int index){
        if(index<array.length){
            int value=array[index];
            if(value!=0){
                TreeNode node=new TreeNode(value);
                array[index]=0;
                node.left=buildTree(array,index*2);
                node.right=buildTree(array,index*2+1);
                return node;
            }
        }
        return null;
    }

深度优先遍历二叉树

思路

采用递归
1.先序遍历：根左右 1245367
2.中序遍历：左根右 4251637
3.后序遍历：左右根 4526731

代码

  //先序，深度优先遍历
    public static void fun(TreeNode tree) {
        if (tree == null) {
            return;
        }
        System.out.println(tree.val);
        if (tree.left != null) {
            fun(tree.left);
        }
        if (tree.right != null) {
            fun(tree.right);
        }
    }

广度优先遍历二叉树

思路

1.利用队列

代码

//广度优先遍历
    public static void fun1(TreeNode tree) {
        LinkedList<TreeNode> list = new LinkedList<>();
        if (tree == null) {
            return;
        }
        list.add(tree);
        while (list.size() != 0) {
            TreeNode n = list.get(0);
            System.out.println(n.val);
            list.remove(0);
            if (n.left != null) {
                list.add(n.left);
            }
            if (n.right != null) {
                list.add(n.right);
            }
        }
    }