A Lin learning algorithm of some notes, write out to remember!

Why do trees exist?

Singly linked lists are too slow to access. To access the middle or last nodes, you have to go back from the beginning one by one.

At this point, bidirectional linked lists appeared, which not only had successors, but also had precursors, making the list access faster.

Then someone thought, why can’t a linked list have multiple Pointers to Next, so that the nodes bifurcated, and a tree was born.

So a tree can be thought of as a specialized linked list.

Basic concepts of trees

The tree in the data structure is a simplification of the tree in the real world: the root is abstracted as “root node”, the branch is abstracted as “edge”, the two endpoints of the branch are abstracted as “node”, and the leaf is abstracted as “leaf node”. The tree structure after abstraction is as follows:

Invert the abstract tree to get the computer tree structure:

A tree has the following definitions:

  • The hierarchy calculation rules of the tree: the layer where the root node is located is the first layer, the child node is the second layer, and so on.
  • The “height” calculation rule of node and tree: the height of leaf node is denoted as 1, and the height of the target node is increased by 1 for each layer of the node. The value obtained is the height of the target node when the node is accumulated layer by layer. The maximum height of a node in a tree is called the height of the tree.
  • The concept of “degree” : how many subtrees a node forks out, which is denoted as the “degree” of the node. For example, in the figure above, the degree of the root is 3.
  • “Leaf nodes” : Leaf nodes are nodes with degree 0. In the figure above, the degree of the nodes in the last layer is all 0, so the nodes in this layer are leaf nodes.

Binary tree

A tree in which the degree of each node is not greater than 2 and each node has at most two next Pointers

Binary tree code implementation

In JS, binary trees are defined using objects. Its structure is divided into three parts:

  • Data fields
  • A reference to the left child (left child root)
  • A reference to the right child (right child root)
function TreeNode (val, left, right) {
  this.val = (val === undefined ? 0 : val)
  this.left = (left === undefined ? null : left)
  this.right = (right === undefined ? null : right)
}

const node = new TreeNode(1)
Copy the code

Binary search tree

Scientists invented the tree data structure to solve practical problems in essence. If the two Pointers of a binary tree point to very chaotic data, it is actually an inefficient data structure with few practical application scenarios.

So they designed a binary search tree to make the left subtree smaller than the right subtree, so that the search would be more efficient.

Binary search tree, also known as ordered binary tree, sorted binary tree, refers to an empty tree or binary tree with the following properties:

  1. If the left subtree of any node is not empty, the value of all nodes in the left subtree is less than the value of its root node.

  2. If the right subtree of any node is not empty, the value of all nodes in the right subtree is greater than the value of its root node.

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

Binary search tree lookups are as efficient as binary lookups, but inserts and deletes are more efficient than arrays.

operation An array of Binary search tree
To find the O(logn) O(logn)
insert O(n) O(logn)
delete O(n) O(logn)

However, if the binary search tree is not balanced, the worst case time complexity of access, insert and sort is O(n).

Actually, scientists have solved this problem for a long time. In real business scenarios, databases use better data structures and post them first.

Leetcode tree first experience

Middle order traversal of binary trees

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

  • Sequential traversal: root -> left subtree -> right subtree
  • Middle order traversal: left subtree -> root -> right subtree
  • Back-order traversal: left subtree -> right subtree -> root

In these three orders, the root traversal is arranged in the first, middle, and last positions, respectively. The so-called “preorder”, “middle order” and “after order”, “first”, “middle”, “after” actually refers to the root traversal machine.

Code implementation

const inorderTraversal = function (root) { const res = [] const inorder = (root) => { if (! Root) {return false} inorder(root.left) // left -> root -> right res.push(root.val) inorder(root.right)} inorder(root) return res }Copy the code

Time complexity: O(n)

Spatial complexity: O(n), the spatial complexity depends on the stack depth of the recursion, and the stack depth is O(n) in the case of a binary tree as a chain.

The same tree

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

Code implementation

const isSameTree = function (p, q) { if (! p && ! Q) {return true} if (! p || ! Q) {return false} if (p.val! == q.val) {// p and q have different val, Return isSameTree(p.left, q.left) &&issametree (p.right, q.right)}Copy the code

Time complexity: O(min(m,n)), where M and n are the nodes of two binary trees respectively. The depth-first search is performed on two binary trees at the same time. The node is accessed only when the corresponding nodes in the two binary trees are not empty. Therefore, the number of nodes accessed cannot exceed the number of nodes in the smaller binary tree.

Space complexity: O(min(m,n)), where M and n are the nodes of two binary trees respectively. The spatial complexity depends on the number of levels of recursive calls, which do not exceed the maximum height of the smaller binary tree, which in the worst case equals the number of nodes.

Symmetric binary tree

You are given a binary tree root node, check whether it is axisymmetric.

Code implementation

const isSymmetric = function (root) { const isMirror = (l, r) => { if (! l && ! R) {// return true} if (! l || ! R) {// return false} if (l.val! == r.val) {// l and r are not equal, Return isMirror(l.ight, r.ight) &&ismirror (L.ight, r.ight)} return isMirror(root, root) }Copy the code

Time complexity: O(n)

Space complexity: O(n)

The maximum depth of a 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.

Code implementation

const maxDepth = function (root) { if (! Else {const l = maxDepth(root.left) // maxDepth(root.left); Const r = maxDepth(root.right) return math.max (l, r) + 1}}Copy the code

Time complexity: O(n)

Space complexity: O(height), where height represents the height of the binary tree.

summary

  • Trees are nothing more than specialized lists, and it’s easy to know why.
  • Usually written algorithm problems are binary tree or binary search tree.
  • Real business scenarios, such as databases, use more efficient trees.

Js tree this data structure is too important, DOM is a tree structure, usually developed a lot of components, such as menu, drop-down selection, etc., also want to support tree structure, understand these basic concepts is very useful.