The maximum depth of a binary tree

The maximum depth of the binary tree, layer by layer after traversing, the first thought is the while loop, but in the process of writing, I found that I could not write down, could not do the sum, could not do the maximum depth of the left subtree and the right subtree.

Then I thought of recursion, but I had no idea, worried…

After reading the official solution, I sorted out my thoughts:

1. Use recursion.

2. The final point in recursion is null, and 0 is returned.

The parent of a null child node is not null, so we need to add depth +1.

4. Use math.max (a,b) to get the maximum depth of left and right subtrees.

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            return Math.max(left, right) + 1; }}}Copy the code

Sequential traversal of binary trees

Every time I look at the official thinking, I feel like I’m not speaking human language… You can only understand it by looking at the solution.

In order to perform the sequence traversal, we need to fetch all the layers of the binary tree, and each layer needs to be from left to right, and the elements of the next layer also need to be from left to right, so we should take out the elements of the K layer and add them to the end of the queue. FIFO features manage the queue.

Note that: when traversing each layer, the number of elements in this layer is equal to the length of the queue, and new elements are constantly added to the queue during the traversal, so the length of the queue needs to be assigned to a variable in advance.

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        while(! queue.isEmpty()) { List<Integer> list =new ArrayList<Integer>();
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);

                if(node.left ! =null) {
                    queue.offer(node.left);
                }
                if(node.right ! =null) {
                    queue.offer(node.right);
                }
            }
            result.add(list);
        }
        returnresult; }}Copy the code

Sequence traversal of binary trees II

This problem is very similar to the last one, and the idea is basically the same, but it turns out that you need to start at the lowest child node and end at the root node. Reverse () = reverse() = reverse() = reverse() = reverse(

We used ArrayList as the final List. We can use LinkedList because it is more efficient to add (index, T) elements.

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        List<List<Integer>> result = new LinkedList<List<Integer>>();

        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        while(! queue.isEmpty()) { List<Integer> list =new ArrayList<Integer>();
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);

                if(node.left ! =null) {
                    queue.offer(node.left);
                }
                if(node.right ! =null) {
                    queue.offer(node.right);
                }
            }
            result.add(0, list);
        }
        returnresult; }}Copy the code

That’s all for today