The road of algorithm

string

The list

An array of

The sum of the range of binary search tree

Given root of the binary search tree, return the sum of the values of all nodes in the range [low, high].

Leetcode-cn.com/problems/ra…

public int rangeSumBST(TreeNode root, int low, int high) { // if (root == null) { // return 0; // } // if (root.val > high) { // return rangeSumBST(root.left, low, high); // } // if (root.val < low) { // return rangeSumBST(root.right, low, high); // } // return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high); int sum = 0; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (! queue.isEmpty()) { TreeNode node = queue.poll(); if (node == null) { continue; } if (node.val > high) { queue.offer(node.left); } else if (node.val < low) { queue.offer(node.right); } else { sum += node.val; queue.offer(node.left); queue.offer(node.right); } } return sum; }Copy the code

2 Print binary tree II from top to bottom

The binary tree is printed from top to bottom layer, with nodes of the same layer printed from left to right, each layer printed to a row.

For example, given a binary tree: [3,9,20,null,null,15,7],

3
Copy the code

/ 9 20/15 7 Returns the result of its hierarchy traversal:

[[3], [9,20], [15,7]

Leetcode-cn.com/problems/co…

Queue<TreeNode> queue = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); if (root ! = null) { queue.add(root); } while (! queue.isEmpty()) { List<Integer> tmp = new ArrayList<>(); for (int i = queue.size(); i > 0; i--) { TreeNode node = queue.poll(); tmp.add(node.val); if (node.left ! = null) { queue.add(node.left); } if (node.right ! = null) { queue.add(node.right); } } res.add(tmp); } return res; }Copy the code

3 Right view of the binary tree

Given a binary tree, imagine yourself standing on the right side of it and return the values of the nodes visible from the right side, in order from top to bottom.

Example:

Input: [1,2,3, NULL,5, NULL,4] Output: [1, 3, 4]

1 <– / 2 3 <– \ 5 4 <–

Source: LeetCode

Link: leetcode-cn.com/problems/bi…

List<Integer> res = new ArrayList<>(); public List<Integer> rightSideView(TreeNode root) { dfs(root,0); return res; } private void dfs(TreeNode root, int depth){ if (root == null) { return; } if(depth == res.size()){ res.add(root.val); } depth++; dfs(root.right,depth); dfs(root.left,depth); }}Copy the code

Balanced binary tree

Input the root node of a binary tree to determine whether the tree is a balanced binary tree. A binary tree is a balanced binary tree if the depth difference between the left and right subtrees of any node is no more than 1.

private boolean result = true; public boolean isBalanced(TreeNode root) { maxDepth(root); return result; } public int maxDepth(TreeNode root) { if (root == null){ return 0; } int l = maxDepth(root.left); int r = maxDepth(root.right); if (Math.abs(l - r) > 1){ result = false; } return 1 + Math.max(l, r); }}Copy the code

5 Minimum depth of the binary tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.

Note: Leaf nodes are nodes that have no child nodes.

 

Example 1:

Input: root = [3,9,20,null,null,15,7] output: 2

Source: LeetCode

Link: leetcode-cn.com/problems/mi…

        if(root == null){
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);

        return (left == 0 || right == 0) ? (left+right+1):Math.min(left,right)+1; 
    }
Copy the code

6 Maximum depth of the binary tree

Given a binary tree, find its maximum depth.

The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.

Note: Leaf nodes are nodes that have no child nodes.

Example: given a binary tree [3,9,20,null,null,15,7],

3
Copy the code

/ 9 20/15 7 Returns its maximum depth of 3.

Source: LeetCode

Link: leetcode-cn.com/problems/ma…

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

7 Order traversal of binary tree

Given a binary tree, return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right).

public List<List<Integer>> levelOrder(TreeNode root) { if(root == null){ return new ArrayList<>(); } LinkedList<TreeNode> queue=new LinkedList<TreeNode>(); List<List<Integer>> resList=new ArrayList<List<Integer>>(); queue.add(root); while(! queue.isEmpty()){ int size = queue.size(); List<Integer> list=new ArrayList<Integer>(); 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); } } resList.add(list); } return resList; }Copy the code