This paper mainly explains the algorithm of binary tree correlation; Because array and linked list are linear structures, it can be easily solved by loop iteration. However, binary tree is a tree structure, and related problems are difficult to be solved by iteration. Therefore, the general solutions are recursive methods.

This topic describes binary tree TreeNode nodes

First, let’s introduce the node class of binary tree we used in this paper. The main purpose of this paper is to solve the problems related to Leetcode. Therefore, the node does not use generics, but directly uses int. If you are defining a data structure, you need to use generics to store node information.

The member variable val represents the information stored in the node. The left node represents the left subtree and the right node represents the right subtree. Three constructors, no arguments, one argument, three arguments;

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() { } TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }}Copy the code

1. Leetcode144 — Preorder traversal of binary tree

Give you the root node of the binary tree, root, and return a pre-traversal of its node value.

Such as:

Input: root = [1,null,2,3] output: [1, 3]

First define the List to store the results, then save the node value to result at the previous traversal position, and return result.

List<Integer> result = new ArrayList<>(); Public List<Integer> preorderTraversal(TreeNode root) {return traversal (TreeNode root); } result.add(root.val); preorderTraversal(root.left); preorderTraversal(root.right); return result; }Copy the code

2, the binary tree before traversal application 1– all nodes value increment 1

The solution is shown as follows: to increase the value of all nodes in the binary tree by 1, we only need to operate the node at the position traversed in the previous order and let the node value increase automatically.

Public void plusOne(TreeNode root) {if (root == null) {return; public void plusOne(TreeNode root) {return; } root.val++; plusOne(root.left); plusOne(root.right); }Copy the code

2– judge whether two binary trees are exactly the same

The solution of the problem is as follows. The recursive termination conditions of this problem are divided into three cases. If two words are empty, the explanation is the same. If one tree is empty and the other tree is not empty, it is different; If the node values are different, the two trees are different.

The recursive process is relatively simple, that is, the recursive call to compare the left and right subtrees of two trees are exactly the same;

Public Boolean isSameTree(TreeNode root1, TreeNode root2) {if (root1 == null && root2 == null) {return true; } / / a tree is empty, the other is not null must not identical if (root1 = = null | | root2 = = null) {return false. } // If (root1.val! = root2.val) { return false; } return isSameTree(root1.left, root2.left) && isSameTree(root1.right, root2.right); }Copy the code

4, binary tree preorder traversal application — judge whether a binary tree is a binary search tree

Binary search tree means that the value of any node in the binary tree is greater than the value of all nodes in the left subtree. And less than all nodes in the right subtree;

Because min represents the minimum value of binary search tree with root as the root node; Max represents the maximum value of the binary search tree with root as the root node. Therefore, if root is less than or equal to min in the recursive termination condition, it means that it is not a binary search tree; Similarly, a root value greater than or equal to Max is not a binary search tree;

The recursive process is to recursively determine whether the left and right subtrees of root node are a binary search tree.

Public Boolean isValidBST(TreeNode root) {return isValidBST(root, null, null); public Boolean isValidBST(TreeNode root) {return isValidBST(root, null, null); } //min represents the minimum value of the binary search tree with root as the root node; Max indicates the maximum value of the binary search tree with root as the root node. Private Boolean isValidBST(TreeNode root, TreeNode min, TreeNode Max) {if (root == null) {return true; } if (min ! = null && root.val <= min.val) { return false; } if (max ! = null && root.val >= max.val) { return false; } return isValidBST(root.left, min, root) && isValidBST(root.right, root, max); }Copy the code

Leetcode94 — Middle order traversal of binary trees

Given the root node of a binary tree, return its middle-order traversal.

Such as:

Input: root = [1,null,2,3]

The solution is as follows: first create a List to save the results, then save the node values in the binary tree where the order traversal, and finally return the List.

List<Integer> result = new ArrayList<>(); // List<Integer> result = new ArrayList<>(); public List<Integer> inorderTraversal(TreeNode root) { if (root == null) { return result; } inorderTraversal(root.left); result.add(root.val); inorderTraversal(root.right); return result; }Copy the code

Leetcode145 — Post-order traversal of binary trees

Given a binary tree, return its backward traversal.

The solution of the problem is as follows. Comparing pre-order traversal with middle-order traversal, the only difference of post-order traversal is that the position of traversal is after the recursive call of left and right subtrees.

//leetcode145 List<Integer> result = new ArrayList<>(); public List<Integer> postorderTraversal(TreeNode root) { if (root == null) { return result; } postorderTraversal(root.left); postorderTraversal(root.right); result.add(root.val); return result; }Copy the code

Leetcode102 — Sequence traversal of binary trees

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).

Such as:

Binary tree: [3,9,20, null, null, 15, 7] results: [[3], [9], [15, 7]]

The solution of the problem is shown as follows. The sequential traversal of binary tree is mainly based on the data structure of queue and the first-in, first-out nature of queue is applied.

First define the queue, then add root to the queue; Each traverse all the nodes from the queue, which represents one layer, if the traverse all the nodes to the left and right child is empty, not to keep left and right children into the queue in the queue, waiting for the next traversal queue, and then are saved to the List of the next layer, each layer will traverse the List to save to the results of this layer, Finally, if the queue is empty, the traversal is done and the result is returned;

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

Leetcode104 — Maximum depth of 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 / \ 9 20 / \ 15 7 returns its maximum depth of 3.Copy the code

The solution is also easy to understand, as shown below. The recursive termination condition says that zero is returned when root is empty, because an empty tree is zero in height;

Recursive process, first recursively solve the maximum height of the left subtree, and then recursively solve the maximum height of the right subtree, the final result is to take the maximum height of the left subtree and the right subtree plus 1, plus 1 indicates the height of root itself;

// Leetcode104 maximum depth of binary tree Public int maxDepth(TreeNode root) {if (root == null) {return 0; } int leftMaxDepth = maxDepth(root.left); int rightMaxDepth = maxDepth(root.right); return Math.max(leftMaxDepth, rightMaxDepth) + 1; }Copy the code

Leetcode226 — Flip a binary tree

Flip a binary tree.

Example: Input: 4 / \ 27 / \ / \ 13 6 9 Output: 4 / \ 7 2 / \ / \ 9 6 3 1Copy the code

The recursive termination condition returns NULL when root== NULL, because an empty tree is also null when flipped.

The recursive process is exactly the same as swapping two positions in an array. First, save the right subtree of root, then point the right subtree of root to the left subtree of root, and finally point the left subtree of root to the right subtree of temporary root. Root ==null; root==null; Finally, return root;

//leetcode226 inverts a binary tree Public TreeNode invertTree(TreeNode root) {if (root == null) {return null; } TreeNode rightNode = root.right; root.right = root.left; root.left = rightNode; invertTree(root.left); invertTree(root.right); return root; }Copy the code

Leetcode112 — Sum of paths

You are given the root node of the binary tree and an integer targetSum representing the targetSum. Determine if there is a path from the root node to the leaf node in the tree. The sum of all nodes in the path equals the target and targetSum.

A leaf node is a node that has no children.

The recursive termination condition returns true only if both the left and right subtrees are empty, indicating that this is a leaf node, and the value of the node is equal to the current target;

In the recursive process to recursively look for the left and right subtrees of root, because it is looking for the sum of paths in the left and right subtrees, so the target at this time should be the original target minus the current root value; If true is returned either time, such a path exists, and true is returned; If false is returned, it does not exist.

//leetcode112 Find out whether there is a path in the binary tree with root as the root node. Target public Boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) {return false; } if (root.left == null && root.right == null && root.val == targetSum) { return true; } if (hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val)) { return true; } return false; }Copy the code

Leetcode257 — All paths to the binary tree

Given a binary tree, return all paths from the root node to the leaf node.

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

Example: input: 1, 2, 3, 5 / output: [" 1 - > 2 - > 5 ", "1 - > 3]" explanation: all the path of the root node to leaf node as follows: 1 - > 2 - > 5, 1 - > 3Copy the code

If both the left and right subtrees of root are empty, root is a leaf node. In this case, the string can be stored in the result. When root is not a leaf, recursively call the left and right subtrees of the current root to add the value of the path to the string.

Public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>(); // Leetcode257 BinaryTreaths (TreeNode root) {List<String> res = new ArrayList<>(); if (root == null) { return res; } solve(root, "", res); return res; } private void solve(TreeNode root, String cur, List<String> res) { if (root == null) { return; } cur = cur + root.val; if (root.left == null && root.right == null) { res.add(cur); return; } solve(root.left, cur + "->", res); solve(root.right, cur + "->", res); }Copy the code

Leetcode111 — Minimum depth of 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.

The solution is shown below. In fact, finding the minimum depth of binary tree is a typical application of sequence traversal. When we traverse layer by layer, the first layer without nodes is the shortest layer, which is the lowest depth; Therefore, the logic is exactly the same as the sequence traversal, except that when the left and right subtrees of the loop node are empty, it will return directly, because the left and right subtrees are empty, which means that the leaf node is;

Public int minDepth(TreeNode root) {if (root == null) {return 0; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int depth = 1; while (! queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode remove = queue.remove(); if (remove.left == null && remove.right == null) { return depth; } if (remove.left ! = null) { queue.add(remove.left); } if (remove.right ! = null) { queue.add(remove.right); } } depth++; } return depth; }Copy the code

Leetcode235 — the most recent common ancestor of binary search trees

Given a binary search tree, find the most recent common ancestor of two specified nodes in the tree.

The definition of the nearest common ancestor in Baidu encyclopedia is: “For the two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, satisfying that X is the ancestor of P and Q and x is as deep as possible (a node can also be its own ancestor).

The solution is as follows, recursive termination condition, when a node is equal to root node, directly return the current node;

In the recursive process, we make use of the properties of binary search tree. When the values of P and Q are both larger than those of root, the nearest common ancestor must be in the right subtree of root, so we recursively search for it in the right subtree. Similarly, if the values of p and q are both smaller than those of root, then the nearest common ancestor must be in the left subtree of root. Other cases indicate that one is larger and one is smaller than root, so the most recent common ancestor must be root;

Public TreeNode lowestCommonAncestor(TreeNode root, TreeNode P, TreeNode q) { if (p.val == root.val) { return p; } if (q.val == root.val) { return q; } if (p.val > root.val && q.val > root.val) { return lowestCommonAncestor(root.right, p, q); } else if (p.val < root.val && q.val < root.val) { return lowestCommonAncestor(root.left, p, q); } else { return root; }}Copy the code

Here are a few general operations for binary search trees

Find the existence of a number in a binary search tree

Return false if root==null; return true if target = root; If the value of root is greater than the value of target, recursively search the left subtree of root; otherwise, recursively search the right subtree of root.

// Find a number in the binary search tree. Public Boolean isInBST(TreeNode root, int target) {if (root == null) {return false; } if (root.val == target) { return true; } if (target < root.val) { return isInBST(root.left, target); } else { return isInBST(root.right, target); }}Copy the code

Insert a number into the binary search tree

We cannot save duplicate elements by default, so we return the current root if val equals target. If root==null, the recursion is complete. When the added element is larger than the current root, it is added to the right subtree of the current root. When the added element is smaller than the current root, it is added to the left subtree of root.

Public TreeNode insertIntoBST(TreeNode root, TreeNode root, int target) { if (root == null) { return new TreeNode(target); } if (root.val == target) { return root; } if (root.val < target) { root.right = insertIntoBST(root.right, target); } if (root.val > target) { root.left = insertIntoBST(root.left, target); } return root; }Copy the code

Delete nodes from binary search tree

Deleting a node from a binary search tree is the most troublesome operation, because there are several different cases of deleting elements, and the structure of the binary search tree must be preserved after deleting elements.

If the value of root is equal to target, it indicates the node to be deleted. Otherwise, continue to recursively search for nodes to be deleted in the left and right subtrees;

There are three cases when the node to be deleted is found. If both the left and right subtrees of the node to be deleted are empty, it indicates that the node is a leaf node, and null is returned directly after deletion. If one of the left and right subtrees of the node to be deleted is empty, you need to return the left and right subtrees to replace the deleted node. About when to delete the node subtree is not empty, first find the node is to be deleted the least of the right subtree of that node, then amend the value of the node is to be deleted to the value of the minimum node in the right subtree, finally will be in the right subtree of the smallest delete node deletion, right subtree minimum node left subtree must be empty, So that translates to the deletion of the second case above;

In fact, a little skill is used here, that is, the value of the smallest node in the right subtree of the node to be deleted is replaced by the value of the node to be deleted, and then the smallest node is deleted, but the node to be deleted is not deleted. However, when the information stored in the Node Node data structure is very complex, we cannot delete it by modifying the Node information. Instead, we should modify the pointer to perform the real deletion operation.

Public TreeNode deleteNode(TreeNode root, TreeNode root, int target) { if (root == null) { return null; If (root.left == null && root.right == null) {return null; if (root.left == null && root.right == null) {return null; } // If (root.left == null) {return root.right; if (root.left == null) {return root.right; } if (root.right == null) { return root.left; } // TreeNode rightMin = minNode(root.right); root.val = rightMin.val; root.right = deleteNode(root.right, rightMin.val); } if (root.val < target) { root.right = deleteNode(root.right, target); } if (root.val > target) { root.left = deleteNode(root.left, target); } return root; } private TreeNode minNode(TreeNode root) { while (root.left ! = null) { root = root.left; } return root; }Copy the code

Source:

Source: LeetCode link: leetcode-cn.com/problemset/…