One, foreword

This topic examines the basic concepts and operations of binary trees.

1. Basic concepts

A tree is a nonlinear data structure often used in computer science. It stores data in a hierarchical form. Binary tree is a special tree structure, each node has at most two subtrees, usually called “left subtree” and “right subtree”.

Using the above picture as an example, some terms related to binary trees are introduced:

  • Degree of node: the number of subtrees owned by node. In the figure, the degree of node 7 is 2.

  • Leaf node: the node whose degree is 0. Node 2 in the figure is a leaf node.

  • Node hierarchy: The layer of the root node is defined as 1, and the child of the root node is the second layer node, and so on.

  • Tree depth: the largest node layer in the tree. The tree depth in the figure is 3.

In JavaScript, you can create TreeNode objects to describe the nodes of the tree:


     
    
      
    function TreeNode(val) {
    
      
      this.val = val;
    
      
      this.left = this.right = null;
    
      
    }
    
     
Copy the code

Binary Search Tree (Binary Search Tree) has the following properties:

  • If the left subtree of any node is not empty, the values of all nodes in the left subtree are less than the values of its root node.

  • If the right subtree of any node is not empty, the values of all nodes in the right subtree are greater than the values of its root node.

  • The left and right subtrees of any node are binary search trees respectively.

  • There are no nodes with equal keys.

Compared with other data structures, the advantage of binary search tree is that the time complexity of search and insertion is O(logn), and an ordered sequence can be obtained after the middle-order traversal operation, which makes it a frequent topic.

2. Basic operations

Binary trees often examine problems based on the following operations:

  • Calculate the depth of binary tree;

  • Sequential traversal: first visits the root, then traverses the left subtree, and finally traverses the right subtree;

  • Middle order traversal: first middle order traverses the left subtree, then visits the root, and finally middle order traverses the right subtree.

  • Back-order traversal: first back-order traversal of the left subtree, then back-order traversal of the right subtree, and finally access the root;

  • Hierarchical traversal: access by node hierarchy;

Binary tree is very suitable for recursive processing. Although recursion is very memory consuming, the code written by it is very readable. In addition, it can be optimized for iteration by JavaScript engine through tail recursion, thus greatly optimizing the time and space complexity.

104. The maximum depth of a binary tree

Given a binary tree, find its maximum depth.

This is a calculation of the depth of the binary tree topic, using the recursive idea: constantly calculate the depth of the subtree, you can get the depth of the entire binary tree.

Questions of the same type:

  • [111. Minimum depth of binary tree];

144. Foreorder traversal of binary trees

Given a binary tree, return its prior traversal.

The use of recursion to achieve binary tree traversal before the code, readable very strong:

The same implementation of sequence traversal and post sequence traversal, is not a piece of cake!

783. Minimum distance of binary search tree node

Given root of a binary search tree, return the minimum difference between any two nodes in the tree.

The middle order traversal sequence of binary search tree is increasing sequence.

Questions of the same type:

  • [530. Minimum absolute difference of binary search tree];

  • [897. Ascending order search tree];

  • [653. Sum of two numbers IV – enter BST];

563. The slope of binary trees

Given a binary tree, calculate the slope of the entire tree. The slope of a node in a tree is defined as the absolute value of the difference between the sum of the nodes of the left subtree and the sum of the nodes of the right subtree. The slope of the null node is 0. The slope of a tree is the sum of the slopes of all its nodes.

Solution idea: In the process of sequential traversal, the sum of the left and right subtrees is calculated first, then the slope of the current node is calculated, and finally the sum of the current subtree is updated.

107. Hierarchical traversal of binary trees II

Given a binary tree, return a bottom-up hierarchical traversal of its node values. (that is, from the layer where the leaf node is located to the layer where the root node is located, layer by layer from left to right)

Queue and stack

The first approach: use stacks and queues to maintain the nodes accessed by each layer.

2, the recursion

The second method: use the recursive idea to record the corresponding hierarchy during the preceding traversal.

Questions of the same type:

  • [637. Level mean of binary trees];

  • [872. Trees with similar leaves];

Vii. 938. The sum of the range of binary search trees

Given root of the binary search tree, return the sum of the values of all nodes between L and R (inclusive). Binary search trees are guaranteed to have unique values.

The binary search tree is a binary search tree. The binary search tree is a binary search tree.

Questions of the same type:

  • [700. Search in binary search tree];

  • [669. Pruning binary search trees];

  • [538. Convert binary search tree to summation tree];

8.100. The same tree

Given two binary trees, write a function to check if they are the same. Two trees are considered identical if they are structurally identical and the nodes have the same value.

If the root node, left subtree and right subtree are all equal, then the two trees must be equal.

Questions of the same type:

  • [572. Subtree of another tree];

  • [101. Symmetric binary tree];

  • [226. Flipping binary trees];

Write in the last

Algorithms as basic computer disciplines, using JavaScript brush, there is no loss of ε=ε=ε= old (゜ _ ゜ロ゜;) ┛.

This series of articles will provide summaries of each algorithm on three levels of difficulty (easy, medium, and hard). In the simple difficulty, we will introduce the basic knowledge and implementation of the algorithm, and in the other two difficulties, we will focus on the idea of solving the problem.

In each summary, some key topics will be selected and explained. For a complete list of problems, please refer to “LeetCode Journey of Front End Engineers”.

If this article has helped you, feel free to like it or follow it to encourage bloggers.

  • LeetCode journey for front-end Engineers – Binary Search Easy

  • LeetCode Journey for front-end Engineers — Two-pointer Tips Easy

  • https://github.com/15751165579/LeetCode

Focus on not getting lost.

Quality content we all “watch”