基本概念

1. 节点的度：节点挂接的子树的个数；树的度：所有节点度的最大值
2. 深度：二叉树中任意一个节点到根节点的距离
3. 高度：二叉树中任意一个节点到叶子节点的距离
4. 二叉树基本概念

• 二叉树第i层上最多2^(i-1)个节点
• 完全二叉树和满二叉树的区别：完全二叉树是最后一层缺少若干右边节点
• 对于完全二叉树，如果从上到写从左到右编号为i，左孩子是2i，右孩子是2i+1，根节点是i/2

遍历

递归遍历

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class TreeTraversal {
    public static void main(String[] args) {
//                    1
//            2               3
//         4      5       6       7
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        TreeNode n7 = new TreeNode(7);
        TreeNode n2 = new TreeNode(2,n4,n5);
        TreeNode n3 = new TreeNode(3,n6,n7);
        TreeNode n1 = new TreeNode(1,n2,n3);
        List<Integer> ls = new ArrayList<>();//存储遍历后的列表
        preorder(n1,ls);//根左右：[1, 2, 4, 5, 3, 6, 7]
        System.out.println(ls.toString());ls.clear();
        inorder(n1,ls);//左根右：[4, 2, 5, 1, 6, 3, 7]
        System.out.println(ls.toString());ls.clear();
        postorder(n1,ls);//左右根：[4, 5, 2, 6, 7, 3, 1]
        System.out.println(ls.toString());
    }
    //先序遍历：根左右
    static void preorder(TreeNode r,List<Integer> ls){
        if(r == null) return;
        ls.add(r.val);
        preorder(r.left,ls);
        preorder(r.right,ls);
    }
    //中序遍历：左根右
    static void inorder(TreeNode r,List<Integer> ls){
        if(r == null) return;
        inorder(r.left,ls);
        ls.add(r.val);
        inorder(r.right,ls);
    }
    //后序遍历：左右根
    static void postorder(TreeNode r,List<Integer> ls){
        if(r == null) return;
        postorder(r.left,ls);
        postorder(r.right,ls);
        ls.add(r.val);
    }
}

非递归遍历

层序遍历

    static void levelOrder(TreeNode r,List<List<Integer>> lls){
        Queue<TreeNode> que = new ArrayDeque<>();
        if(r == null) return;
        que.add(r);//根节点入队
        while(!que.isEmpty()){
            ArrayList<Integer> ls = new ArrayList<>();//存储每一层节点的值
            for (int i = 0; i < que.size(); i++) {
                //每出队一个就把这个节点的左右孩子都入队
                TreeNode node = que.poll();//1.每一层节点分别出队
                ls.add(node.val);//2.把出队节点的值放进ls
                if(node.left != null) que.add(node.left);//3.左节点入队
                if(node.right != null) que.add(node.right);//3.右节点入队
            }
            lls.add(ls);
        }
    }

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

    public int maxDepth(TreeNode root) {
        //根节点的高度，其实就是树的最大深度
        //这里是后序遍历求根节点的高度
        //递归对每一个节点求高度
        if(root==null) 
            //叶子节点高度为1，它的空孩子节点高度为0
            return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth,rightDepth)+1;
    }

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

    public int minDepth(TreeNode root) {
        //这道题中最小深度的定义特殊，是根节点到最近叶子节点的距离
        //左子树或右子树的高度有一个为null，就算另一个不为空的子树的高度
        //二叉树的最小深度，等价于求根节点的最小高度
       if(root==null) return 0;
       int left = minDepth(root.left);
       int right = minDepth(root.right);
       if(root.left==null&&root.right!=null){
           //如果左子树为空，就计算右子树的最小高度
           return 1 + right;
       }
       if(root.right==null&&root.left!=null){
           //如果右子树为空，就计算左子树的最小高度
           return 1 + left;
       }
       //如果两个都不为空，就计算它们的最小值
       return 1 + Math.min(left,right);
    }