新手入门篇-二叉树的面试案例-灵析社区

二叉树按层遍历并收集节点

思路：

拿出此时队列的size，size有多少，弹出多少
弹出节点，先左后右放进去

注意：

LinkedList比ArrayList效率高，LinkedList底层通过链表实现，且是双端队列
每轮队列的size，必须用临时变量接受，也就是需要弹出固定的size

public class Code01_BinaryTreeLevelOrderTraversalII {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> ans = new LinkedList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> curAns = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.poll();
                curAns.add(curNode.val);
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            ans.addFirst(curAns);
        }
        return ans;
    }
}

判断一颗树是否是平衡二叉树

平衡二叉树的定义

任意子树中，|left的高度 - right的高度| <= 1

思路

假设任意节点的左子树平衡，右子树平衡，并且左子树的高度-右子树的绝对值小于等于1，则认为当前节点下都平衡。

public class Code02_BalanceBinaryTree {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public boolean isBalanced(TreeNode root) {
        return process(root).isBalanced;
    }

    public static class Info {
        public boolean isBalanced;
        public int height;

        public Info(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

    public static Info process(TreeNode root) {
        if (root == null) {
            return new Info(true, 0);
        }
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        boolean isBalanced = leftInfo.isBalanced && rightInfo.isBalanced
                && Math.abs(leftInfo.height - rightInfo.height) < 2;
        return new Info(isBalanced, height);
    }
}

递归轨迹如下图

判断一棵树是否是搜索二叉树

搜索二叉树的定义

Binary Search Tree，任意节点的left都比当前节点小，right都比当前节点大

思路

判断当前节点是否满足BST

当前节点的左子树中最大值都比当前节点的值小
当前节点的右子树中最小值都比当前节点的值大

public class Code03_IsBinarySearchTree {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static class Info {
        public boolean isBST;
        public int max;
        public int min;

        public Info(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

    public static Info process(TreeNode x) {
        if (x == null) {
            return null;
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int max = x.val;
        int min = x.val;
        if (leftInfo != null) {
            max = Math.max(leftInfo.max, max);
            min = Math.min(leftInfo.min, min);
        }
        if (rightInfo != null) {
            max = Math.max(rightInfo.max, max);
            min = Math.min(rightInfo.min, min);
        }
        boolean isBST = true;
        if (leftInfo != null && !leftInfo.isBST) {
            isBST = false;
        }
        if (rightInfo != null && !rightInfo.isBST) {
            isBST = false;
        }
        boolean leftMaxLessX = leftInfo == null ? true : leftInfo.max < x.val;
        boolean rightMixMoreX = rightInfo == null ? true : rightInfo.min > x.val;
        if (!(leftMaxLessX && rightMixMoreX)) {
            isBST = false;
        }
        return new Info(isBST, max, min);
    }
}

判断一颗树是否是平衡搜索二叉树

平衡搜索二叉树的定义

满足平衡二叉树且满足搜索二叉树

代码就不写了，判断平衡二叉树code && 判断搜索二叉树

总结

本篇介绍了二叉树面试高频的案例，算法练习其实对coding的能力是有帮助的。多多练习，必有回报！