面试算法代码知识梳理系列

面试算法知识梳理(1) - 排序算法
面试算法知识梳理(2) - 字符串算法第一部分
面试算法知识梳理(3) - 字符串算法第二部分
面试算法知识梳理(4) - 数组第一部分
面试算法知识梳理(5) - 数组第二部分
面试算法知识梳理(6) - 数组第三部分
面试算法知识梳理(7) - 数组第四部分
面试算法知识梳理(8) - 二分查找算法及其变型
面试算法知识梳理(9) - 链表算法第一部分
面试算法知识梳理(10) - 二叉查找树
面试算法知识梳理(11) - 二叉树算法第一部分
面试算法知识梳理(12) - 二叉树算法第二部分
面试算法知识梳理(13) - 二叉树算法第三部分

---

一、概述

在 算法知识梳理(10) - 二叉查找树 中，我们简要介绍了二叉查找树的基本概念、插入及删除操作，今天这篇文章，以这个为基础，介绍一下和二叉树有关的操作，由于篇幅有限，因此分为三篇文章介绍，第一部分包括：

• 递归遍历二叉树（先序遍历、中序遍历、后序遍历）
• 分层打印二叉树
• 打印二叉树的第n层
• 统计二叉树叶结点的个数
• 统计二叉树的高度

二、代码实现

2.1 递归遍历

解决思路

二叉树的遍历方式有以下三种：

• 先序遍历：根结点 -> 左子树 -> 右子树
• 中序遍历：左子树 -> 根结点 -> 右子树
• 后序遍历：左子树 -> 右子树 -> 根结点

递归的方式比较容易理解，只需要改变函数调用和打印元素值语句之间的顺序即可，例如先序遍历，就先打印该结点元素的值，再分别打印左子树和右子树即可。

代码实现

class Untitled {

    static class Tree {
        int size;
        Node root;
    }

    static class Node {
        Node parent;
        Node left;
        Node right;
        int value;
    }

    static void insertNode(Tree tree, int value) {
        if (tree == null) {
            return;
        }
        Node tNode = tree.root;
        //待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
        Node pNode = null;
        //新的结点。
        Node nNode = new Node();
        nNode.value = value;
        while (tNode != null) {
            pNode = tNode;
            if (tNode.value > value) {
                tNode = tNode.left;
            } else {
                tNode = tNode.right;
            }
        }
        nNode.parent = pNode;
        if (pNode == null) {
            tree.root = nNode;
        } else if (pNode.value > value) {
            pNode.left = nNode;
        } else {
            pNode.right = nNode;
        }
        tree.size++;
    }

    static Tree createBinTree(int p[], int len) {
        Tree tree = new Tree();
        for (int i = 0; i < len; i++) {
            int value = p[i];
            insertNode(tree, value);
        }
        return tree;
    }

    static void printPreOrder(Node node) {
        if (node == null) {
            return;
        }
        //先打印根结点。
        System.out.println(node.value);
        //先遍历左子树。
        printPreOrder(node.left);
        //再遍历右子树。
        printPreOrder(node.right);
    }


    static void printInOrder(Node node) {
        if (node == null) {
            return;
        }
        printInOrder(node.left);
        //遍历完左子树后，打印根结点，最后遍历右子树。
        System.out.println(node.value);
        printInOrder(node.right);
    }

    static void printPostOrder(Node node) {
        if (node == null) {
            return;
        }
        //先遍历右子树。
        printPostOrder(node.right);
        //再遍历左子树。
        printPostOrder(node.left);
        //最后打印根结点。
        System.out.println(node.value);
    }

    public static void main(String[] args) {
        int p[] = {3, 5, 6, 1, 2, 4};
        Tree tree = createBinTree(p, p.length);
        System.out.println("- 先序遍历 - ");
        printPreOrder(tree.root);
        System.out.println("- 中序遍历 - ");
        printInOrder(tree.root);
        System.out.println("- 后序遍历 - ");
        printPostOrder(tree.root);
    }
}

运行结果

- 先序遍历 - 
3
1
2
5
4
6
- 中序遍历 - 
1
2
3
4
5
6
- 后序遍历 - 
6
4
5
2
1
3

2.2 分层打印二叉树

解决思路

假设建立了一棵如下的二叉树，元素3为第一层，1、5为第二层，-1、2、4、6为第三层，要求按照层的顺序依次打印出每一层的所有元素。

二叉树
这里需要借助容器类LinkedList来进行存储下一行的元素，并用end保存每一行的最后一个元素，遍历到该元素时打印换行符来实现分层打印。

代码实现

import java.util.LinkedList;

public class Untitled {

    static class Tree {
        int size;
        Node root;
    }

    static class Node {
        Node parent;
        Node left;
        Node right;
        int value;
    }

    static void insertNode(Tree tree, int value) {
        if (tree == null) {
            return;
        }
        Node tNode = tree.root;
        //待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
        Node pNode = null;
        //新的结点。
        Node nNode = new Node();
        nNode.value = value;
        while (tNode != null) {
            pNode = tNode;
            if (tNode.value > value) {
                tNode = tNode.left;
            } else {
                tNode = tNode.right;
            }
        }
        nNode.parent = pNode;
        if (pNode == null) {
            tree.root = nNode;
        } else if (pNode.value > value) {
            pNode.left = nNode;
        } else {
            pNode.right = nNode;
        }
        tree.size++;
    }

    static Tree createBinTree(int p[], int len) {
        Tree tree = new Tree();
        for (int i = 0; i < len; i++) {
            int value = p[i];
            insertNode(tree, value);
        }
        return tree;
    }

    static void printTreeLevelOrder(Tree tree) {
        if (tree == null || tree.root == null) {
            return;
        }
        Node root = tree.root;
        LinkedList<Node> queue = new LinkedList<>();
        //先放入根结点。
        queue.offer(root);
        //对应于下一层的最后一个元素。
        Node end = root;
        while (!queue.isEmpty()) {
            //取出当前队列中的首结点，并打印它的值。
            Node node = queue.getFirst();
            System.out.print(String.valueOf(node.value));
            //将该结点的左右孩子放入到队列的尾部。
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            //如果当前的结点是该行的尾结点，那么打印一个换行符，并且将 end 赋值为下一行的尾结点。
            if (node == end) {
                System.out.print("\n");
                end = queue.getLast();
            } else {
                System.out.print(" ");
            }
            //将该结点从队列头部删除。
            queue.pop();
        }
    }


    public static void main(String[] args) {
        int p[] = {3, 5, 6, 1, 2, 4, -1, -3};
        Tree tree = createBinTree(p, p.length);
        printTreeLevelOrder(tree);
    }
}

运行结果

>> 3
>> 1 5
>> -1 2 4 6
>> -3

2.3 打印二叉树的第 n 层

解决思路

打印二叉树的第n层和2.2中是相同的原理，只不过是在遍历到第n层时才打印所需的元素。

代码实现

import java.util.LinkedList;

public class Untitled {

    static class Tree {
        int size;
        Node root;
    }

    static class Node {
        Node parent;
        Node left;
        Node right;
        int value;
    }

    static void insertNode(Tree tree, int value) {
        if (tree == null) {
            return;
        }
        Node tNode = tree.root;
        //待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
        Node pNode = null;
        //新的结点。
        Node nNode = new Node();
        nNode.value = value;
        while (tNode != null) {
            pNode = tNode;
            if (tNode.value > value) {
                tNode = tNode.left;
            } else {
                tNode = tNode.right;
            }
        }
        nNode.parent = pNode;
        if (pNode == null) {
            tree.root = nNode;
        } else if (pNode.value > value) {
            pNode.left = nNode;
        } else {
            pNode.right = nNode;
        }
        tree.size++;
    }

    static Tree createBinTree(int p[], int len) {
        Tree tree = new Tree();
        for (int i = 0; i < len; i++) {
            int value = p[i];
            insertNode(tree, value);
        }
        return tree;
    }

    static void printTreeKLevel(Tree tree, int k) {
        if (tree == null || tree.root == null) {
            return;
        }
        Node root = tree.root;
        LinkedList<Node> queue = new LinkedList<>();
        //先放入根结点。
        queue.offer(root);
        //对应于下一层的最后一个元素。
        Node end = root;
        int curLevel = 1;
        while (!queue.isEmpty()) {
            //取出当前队列中的首结点，并打印它的值。
            Node node = queue.getFirst();
            //如果当前位于第k层，那么就打印元素。
            if (curLevel == k) {
                System.out.print(String.valueOf(node.value));
            }
            //将该结点的左右孩子放入到队列的尾部。
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (node == end) {
                curLevel++;
                //如果大于k层，那么就跳出循环。
                if (curLevel > k) {
                    break;
                }
                end = queue.getLast();
            } else {
                System.out.print(" ");
            }
            //将该结点从队列头部删除。
            queue.pop();
        }
    }


    public static void main(String[] args) {
        int p[] = {3, 5, 6, 1, 2, 4, -1, -3};
        Tree tree = createBinTree(p, p.length);
        printTreeKLevel(tree, 3);
    }
}

运行结果

>> -1 2 4 6

2.4 统计二叉树的叶结点个数

解决思路

叶结点指的是没有左右子树的结点，因此二叉树的叶结点个数等于它的左右子树叶结点之和，可以通过递归的方法来实现。

代码实现

public class Untitled {

    static class Tree {
        int size;
        Node root;
    }

    static class Node {
        Node parent;
        Node left;
        Node right;
        int value;
    }

    static void insertNode(Tree tree, int value) {
        if (tree == null) {
            return;
        }
        Node tNode = tree.root;
        //待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
        Node pNode = null;
        //新的结点。
        Node nNode = new Node();
        nNode.value = value;
        while (tNode != null) {
            pNode = tNode;
            if (tNode.value > value) {
                tNode = tNode.left;
            } else {
                tNode = tNode.right;
            }
        }
        nNode.parent = pNode;
        if (pNode == null) {
            tree.root = nNode;
        } else if (pNode.value > value) {
            pNode.left = nNode;
        } else {
            pNode.right = nNode;
        }
        tree.size++;
    }

    static Tree createBinTree(int p[], int len) {
        Tree tree = new Tree();
        for (int i = 0; i < len; i++) {
            int value = p[i];
            insertNode(tree, value);
        }
        return tree;
    }

    static int getLeafNumber(Node node) {
        if (node == null) {
            return 0;
        }
        if (node.left == null && node.right == null) {
            return 1;
        }
        return getLeafNumber(node.left) + getLeafNumber(node.right);
    }

    public static void main(String[] args) {
        int p[] = {3, 5, 6, 1, 2, 4, -1, -3};
        Tree tree = createBinTree(p, p.length);
        System.out.println("叶结点个数=" + getLeafNumber(tree.root));
    }
}

运行结果

>> 叶结点个数=4

2.5 统计二叉树的高度

解决思路

二叉树的高度 为其根结点到叶结点的最大距离，我们可以先求出它的左右子树的高度的最大值，再加上1就可得到以该结点为根结点的二叉树的高度，同样可以采用递归的方式来实现。

代码实现

public class Untitled {

    static class Tree {
        int size;
        Node root;
    }

    static class Node {
        Node parent;
        Node left;
        Node right;
        int value;
    }

    static void insertNode(Tree tree, int value) {
        if (tree == null) {
            return;
        }
        Node tNode = tree.root;
        //待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
        Node pNode = null;
        //新的结点。
        Node nNode = new Node();
        nNode.value = value;
        while (tNode != null) {
            pNode = tNode;
            if (tNode.value > value) {
                tNode = tNode.left;
            } else {
                tNode = tNode.right;
            }
        }
        nNode.parent = pNode;
        if (pNode == null) {
            tree.root = nNode;
        } else if (pNode.value > value) {
            pNode.left = nNode;
        } else {
            pNode.right = nNode;
        }
        tree.size++;
    }

    static Tree createBinTree(int p[], int len) {
        Tree tree = new Tree();
        for (int i = 0; i < len; i++) {
            int value = p[i];
            insertNode(tree, value);
        }
        return tree;
    }

    static int getTreeHeight(Node node) {
        if (node == null) {
            return 0;
        }
        int left = getTreeHeight(node.left) + 1;
        int right = getTreeHeight(node.right) + 1;
        return left > right ? left : right;
    }

    public static void main(String[] args) {
        int p[] = {3, 5, 6, 1, 2, 4, -1, -3};
        Tree tree = createBinTree(p, p.length);
        System.out.println("二叉树高度=" + getTreeHeight(tree.root));
    }
}

运行结果

>> 二叉树高度=4

---

更多文章，欢迎访问我的 Android 知识梳理系列：

• Android 知识梳理目录：http://www.jianshu.com/p/fd82d18994ce
• Android 面试文档分享：http://www.jianshu.com/p/8456fe6b27c4