“This is the 16th day of my participation in the Gwen Challenge.

The last article is data structure and algorithm novice into the fourth chapter, this is data structure and algorithm novice into the fifth chapter, come to experience the charm of the algorithm!

The binary tree traverses layers and collects nodes

Ideas:

1. Take out the size of the queue at this point, how many sizes, how many pops
2. Eject the node, first left and then right

Note:

1. LinkedList is more efficient than ArrayList because the underlying LinkedList is implemented through linked lists and is a two-ended queue
2. The size of each round of the queue must be accepted as a temporary variable, that is, a fixed size needs to pop up

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);
        }
        returnans; }}Copy the code

Determine if a tree is a balanced binary tree

Definition of balanced binary tree

Any subtree, | the height of the height of the left – right | < = 1

Train of thought

Assuming that the left subtree of any node is balanced and the right subtree is balanced, and that the height of the left subtree – the absolute value of the right subtree is less than or equal to 1, then all nodes under the current node are considered balanced.

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 newInfo(isBalanced, height); }}Copy the code

The recursion trajectory is shown below

Determine if a tree is a search binary tree

Search the definition of a binary tree

Binary Search Tree: The left of any node is smaller than the current node and the right is larger than the current node

Train of thought

Check whether the current node meets the BST requirement

1. The maximum value in the left subtree of the current node is smaller than the value of the current node
2. The smallest values in the right subtree of the current node are greater than the value of the current node

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 newInfo(isBST, max, min); }}Copy the code

Determine if a tree is a balanced search binary tree

Definition of balanced search binary tree

Satisfies the equilibrium binary tree and satisfies the search binary tree

I’m not going to write the code, judge the balanced binary tree code && judge the search binary tree

conclusion

This paper introduces the case of binary tree interview frequency, algorithm practice is actually helpful for coding ability. Practice a lot and it will pay off!

Welcome everyone to pay attention to the public account (MarkZoe) to learn from each other and communicate with each other.