This is the 20th day of my participation in the Genwen Challenge

  • A tree is a data structure that is often used to simulate a collection of data with a tree-like structure.

  • Each node in the tree has a root and a list of all its children. From a graph point of view, a tree can also be regarded as a directed acyclic graph with N nodes and N-1 edges.

  • Binary tree is a more typical tree-like structure. As its name suggests, a binary tree is a tree structure in which each node has at most two subtrees, usually referred to as “left subtrees” and “right subtrees”.

  • A full binary tree is called a full binary tree if the number of nodes at the ith level is 2^(i-1).

  • Complete binary tree If the depth of the binary tree is h, the front (h-1) layer is filled (each parent node has two child nodes), the h layer is from left to right, and only the right-most subtree is not filled, the tree is called a complete binary tree.

  • A heap is a special complete binary tree in which the value of any node in the heap is not greater than (less than) the value of its children. (not greater than — minimum heap; Not less than — maximum heap). The heap is, so to speak, a complete binary search tree.

  • Binary sort tree (binary search tree) Binary search tree is a special form of binary tree. Binary search trees have the following property: The value in each node must be greater than (or equal to) any value in its left subtree, but less than (or equal to) any value in its right subtree.

  • A balanced binary tree is an empty tree or the absolute value of the difference in height between the left and right subtrees is no more than 1, and both subtrees are a balanced binary tree. This scheme solves the problem of binary search tree degenerating into linked list well, and keeps the time complexity of insertion, search and deletion in O(logN) at best and at worst. However, frequent rotation causes insertion and deletion to sacrifice order (logN) time, but it is much more stable than binary search trees.

  • Red black tree, it’s a special binary search tree. Red-black trees have memory bits on each node to indicate the color of the node, which can be Red or Black. Characteristics of red-black trees:

    • (1) Each node is either black or red.
    • (2) The root node is black.
    • (3) Each leaf node (NIL) is black. [Note: leaf nodes are NIL or NULL leaf nodes!]
    • (4) If a node is red, its children must be black.
    • (5) All paths from a node to its descendants contain the same number of black nodes.

1 Depth-first traversal

  • Front-order traversal: Front-order traversal first visits the root node, then the left subtree, and finally the right subtree.

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null) {return result;
        }

        result.add(root.val);
        if(root.left ! =null) result.addAll(preorderTraversal(root.left));
        if(root.right ! =null) result.addAll(preorderTraversal(root.right));

        returnresult; }}Copy the code
  • Middle-order traversal: Middle-order traversal traverses the left subtree, then visits the root node, and then traverses the right subtree.

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> resultList = new ArrayList<>();
        if(root == null) {return resultList;
        }
        if(root.left ! =null )resultList.addAll(inorderTraversal(root.left));
        resultList.add(root.val);
        if(root.right ! =null)resultList.addAll(inorderTraversal(root.right));
        returnresultList; }}Copy the code
  • Back-order traversal: Back-order traversal is to traverse the left subtree first, then the right subtree, and finally to visit the root node of the tree.

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

2 Sequence traversal (breadth-first search)

Breadth-first search is a layer-by-layer tour of the tree structure. Breadth-first search is a traversal or search algorithm that is widely used in data structures such as trees or graphs. The algorithm starts with a root node and first accesses the node itself. It then traverses its neighboring nodes, then its second-level neighbors, third-level neighbors, and so on. When we do a breadth-first search in a tree, the order of the nodes we visit is traversal in order. In general, we use the data structure of the queue to help us do breadth-first search.

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) {return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(! queue.isEmpty()){int size = queue.size();
            List<Integer> levelList = new ArrayList<>();
            for(int i = 0; i < size; i++){ TreeNode node = queue.poll();if(node.left ! =null){
                    queue.offer(node.left);
                }
                if(node.right ! =null){
                    queue.offer(node.right);
                }
                levelList.add(node.val);
            }
            result.add(levelList);
        }

        returnresult; }}Copy the code