19|二叉树基础（上）：什么样的二叉树适合用数组来存储？

一、树

tree

1.树的常用概念

比如下面这幅图，A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。我们把没有父节点的节点叫作根节点，也就是图中的节点 E。我们把没有子节点的节点叫作叶子节点或者叶节点，比如图中的 G、H、I、J、K、L 都是叶子节点。

2.树的高度（Height）、深度（Depth）、层（Level）

树的深度 = 层数 - 1

二、二叉树

1.概念

①什么是二叉树？
每个节点最多只有2个子节点的树，这两个节点分别是左子节点和右子节点。

②什么是满二叉树？
有一种二叉树，除了叶子节点外，每个节点都有左右两个子节点，这种二叉树叫做满二叉树。

③什么是完全二叉树？
有一种二叉树，叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。

2.完全二叉树的存储

①链式存储
每个节点由3个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式比较常用，大部分二叉树代码都是通过这种方式实现的。

②顺序存储
用数组来存储，对于完全二叉树，如果节点X存储在数组中的下标为i，那么它的左子节点的存储下标为2i，右子节点的下标为2i+1，反过来，下标i/2位置存储的就是该节点的父节点。注意，根节点存储在下标为1的位置。完全二叉树用数组来存储时最省内存的方式。

3.二叉树的遍历

①前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
②中序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的本身，最后打印它的右子树。
③后序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印它本身。

前序遍历的递推公式：

preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

中序遍历的递推公式：

inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

后序遍历的递推公式：

postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

时间复杂度：3种遍历方式中，每个节点最多会被访问2次，所以时间复杂度是O(n)。

三、思考

1.二叉树有哪几种存储方式？什么样的二叉树适合用数组来存储？

答：链式存储（链表）和顺序存储（数组）。数组顺序存储的方式比较适合完全二叉树，其他类型的二叉树用数组存储会比较浪费存储空间。

2.给定一组数据，比如1，3，5，6，9，10.你来算算，可以构建出多少种不同的二叉树？

答：： n!
3.我们讲了三种二叉树的遍历方式，前、中、后序。实际上，还有另一种遍历方式，也就是按层遍历，你知道如何实现吗？

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<>(0);
        
        List<List<Integer>> result = new ArrayList<>();
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        Queue<TreeNode> curLevelNodes = new LinkedList<TreeNode>();
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            curLevelNodes.offer(node);
            
            if (queue.isEmpty()) {
                List<Integer> list = new ArrayList<>(curLevelNodes.size());
                while (!curLevelNodes.isEmpty()) {
                    TreeNode curNode = curLevelNodes.poll();
                    list.add(curNode.val);
                    
                    if (curNode.left != null) {
                        queue.offer(curNode.left);
                    }
                    
                    if (curNode.right != null) {
                        queue.offer(curNode.right);
                    }
                    
                }
                result.add(list);
            }
        }
        
        
        return result;
    }
    
}