Ergodic summary of binary trees

Binary tree

In my opinion, binary number is to add next nodes with left and right nodes on the basis of linked list, that is, left and right child nodes, through which a binary number is connected in series. A tree of left and right nodes under the root node, also called a left and right subtree.

How do I manipulate binary trees

The operation of binary tree is nothing more than traversal binary tree, there are three traversal of binary number: pre-order traversal, middle-order traversal, follow-up traversal, also known as depth-first traversal, breadth-first traversal, traversal also mainly need two kinds of recursion, iteration, binary tree fire data structure is as follows:

var node = {
	val : 1 ,
    	left : {   // left is the left child node
	  xxx  // Indicates the next node
    	},
        right: {// Right left child node
         xxxx // Indicates the next node}}Copy the code

Leedcode bo

First, the most basic is how to recursively and iteratively traverse binary trees to find their commonalities:

Pre-middle and subsequent traversal of binary trees (leecode144, 94, 145)

Leetcode-cn.com/problems/bi… (preorder traversal of binary tree) leetcode-cn.com/problems/bi… (middle order traversal of binary tree) leetcode-cn.com/problems/bi… (Post-order traversal of binary tree)

The idea of traversal before and after (recursion)

  • The current node is null-terminated recursion
  • Continuation: Add the current node to the result and recurse to the left and right subtrees
  • Continuation: first recurse the left subtree, after the end of the left subnumber recursion, add the current node to the result, and then recurse the right subtree
  • Follow-up: first recurse the left and right subtrees in turn. After the end of the left and right recursion, add the current node to the result.

Complexity analysis

Time complexity: O(n) Space complexity: O(n)

// continue through
var preorderTraversal = function(root) {
    var res= []
    var dfs = (root) = > {
        if(! root)return 
        res.push(root.val)
        dfs(root.left)
        dfs(root.right)
    }
    dfs(root)
    return res
};
// continue to iterate
var preorderTraversal = function(root) {
    var res= []
    var dfs = (root) = > {
        if(! root)return 
        dfs(root.left)
        res.push(root.val)
        dfs(root.right)
    }
    dfs(root)
    return res
};
// subsequent traversal
var preorderTraversal = function(root) {
    var res= []
    var dfs = (root) = > {
        if(! root)return 
        dfs(root.left)
        dfs(root.right)
        res.push(root.val)
    }
    dfs(root)
    return res
};
Copy the code

The idea of traversal before and after (iteration)

  • You can simulate a stack, with the same details as recursion

Complexity analysis

Time complexity: O(n)

Space complexity: O(n)

Five lines of code to go through before and after

// continue through
var preorderTraversal = function(root) {
    var res= []
    var stack = []
    while(root || stack.length) {
        while(root) {
            res.push(root.val) // The continuation first pushes the value into the result
            stack.push(root)  // all left subtrees are pushed in sequence
            root = root.left	
        }
        root = stack.pop() // Unstack if there is no right node continue to unstack
        root = root.right
    }
    return res
};
// continue to iterate
var preorderTraversal = function(root) {
    var res= []
    var stack = []
    while(root || stack.length) {
        while(root) {
            stack.push(root) // All left subtrees are pushed in sequence
            root = root.left
        }
        root = stack.pop() / / out of the stack
        res.push(root.val) // Push the current value of the value into the result
        root = root.right
    }
    return res
};
// subsequent traversal
var preorderTraversal = function(root) {
    var res= []
    var stack = []
    while(root || stack.length) {
        while(root) {         
            res.push(root.val)  // First push the value into the result
            stack.push(root)	// all right subtrees are pushed in sequence through the root node
            root = root.right
        }
        root = stack.pop()  // Unstack if there is no left node continue to unstack
        root = root.left
    }
    return res.reverse() // The order of traversal is right to left, and the last one is right to left => left and right roots
 };
Copy the code

It can be found that I only changed five lines of code and changed their order to complete the pre-middle and subsequent traversal. The pre-middle and post-middle iteration framework is roughly as follows:

While (root) {res.push(root.val) // first push the value to the result stack.push(root) root = root.right} root = stack.pop() // out of the stack root = root.leftCopy the code

Sequence Traversal of binary Trees (BFS) (Leecode102)

Leetcode-cn.com/problems/bi…

Given a binary tree, return the value of the nodes traversed in order. Sequential traversal is to access all nodes layer by layer from left to right

Train of thought

Breadth-first traversal is a layer-by-layer approach that traverses the nodes of each layer. The requirement is to return the node values of each layer, so using breadth-first is quite appropriate.

var levelOrder = function(root) {
    if (root === null)  return []
    var arr = []  // Breadth-first requires queues as auxiliary structures
    var res = []
    arr.push(root) 
    while(arr.length ! = =0) {
        var array = []
        var size = arr.length
        for(var i = 0; i<size; i++) {var cur = arr.shift()  // Take out the root node first
             array.push(cur.val)
            if(cur.left! =null) { // If the left/right subtrees are not empty, they are queued.
            	arr.push(cur.left)
            } 
         	if(cur.right! =null) {
             	arr.push(cur.right)
            } 
        }
       // After the first processing, the root node has been removed from the queue, and the root node's two children have been queued
     res.push(array) // Save the result each time
     // Each loop removes all nodes from the queue and then places the children in the queue.
    }
    return res
};
Copy the code