Tree traversal

Learning Objectives:

• Learning tree traversal;
• Basic knowledge of binary search tree;
• Practice Python syntax;

Leetcode learns traversal of a data tree

Tree traversal:

• Middle order traversal – recursive
• Backward traversal — recursion
• Preorder traversal – recursion
• Sequence traversal

Traverse the template

// (binary tree) backorder traversal
  const postorder=(root) = >{
         if(! root){return;
        }
        postorder(root.left);
        postorder(root.right);
        res.push(root.val);
    }
Copy the code

// (binary tree) order traversal
  const inorder=(root) = >{
         if(! root){return;
        }
        postorder(root.left);
        res.push(root.val);
        postorder(root.right);
    }
Copy the code

  // (binary tree) preorder traversal
  const preorder=(root) = >{
         if(! root){return;
        }
        res.push(root.val);
        postorder(root.left);
        postorder(root.right);
    }
Copy the code

// sequence traversal
const levelOrder=(root) = >{
   / / found empty
   if(! root){return [];
    }
    
    // Initialize the queue
    let queue=[];
    queue.push(root);
    
    // Store the result data
    let res=[];
    
    // loop the queue
    while(queue.length){
       let arr=[];// An array of results for the current layer
       for(let i=0,len=queue.length; i<len; ++i){// Get queue header data and delete queue header data
           let node=queue.shift();
            arr.push(node.val);
            
            // The queue stores the next layer of data
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
       }
       // Store current layer data
       res.push(arr);
    }
    
    // Return the result
    return res;
 }
Copy the code

Binary Search Tree

• Binary search tree features:

1. The value of all nodes in the left subtree is less than the value of its root node;
2. The value of all nodes in the right subtree is greater than the value of its root node;
3. The left and right subtrees are binary search trees respectively.
4. Middle order traversal: ascending order;

• General in-operation of binary search trees

1. Lookup (average time complexity O(logn));
2. Insert (mean time complexity O(logn));
3. Delete (average time complexity O(logn));

Implementation of binary Search tree (Search, Insert, Delete)

practice

• Middle order traversal of binary trees

Language: the JavaScript

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var inorderTraversal = function(root) {
  
    let arr=[];
    const inOrder=(root) = >{
        if(root===null) return;
        inOrder(root.left);
        arr.push(root.val);
        inOrder(root.right);
    }
    inOrder(root);
    return arr;

};
Copy the code

Language: the python

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) - >List[int] :
        res=[];
        def inorder(root) :
            if not root:
                return;
            inorder(root.left);
            res.append(root.val);
            inorder(root.right);
        inorder(root);
        return res;         
Copy the code

• Subsequent traversal of the n-fork tree

Language: the javascript

/** * // Definition for a Node. * function Node(val,children) { * this.val = val; * this.children = children; *}; * /

/ * * *@param {Node|null} root
 * @return {number[]}* /
var postorder = function(root) {
    const res=[];
    const order=(root) = >{
        if(root===null) {return;
        }

        for(let i=0,len=root.children.length; i<len; ++i){ order(root.children[i]); } res.push(root.val); } order(root);return res;
};
Copy the code

Language: the python

""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """

class Solution:
    def postorder(self, root: 'Node') - >List[int] :
        res=[];
        def order(root) :
            if root == None:
                return;
            for item in root.children:
                order(item)
            else:
                res.append(root.val);
        order(root);
        return res;
Copy the code

• Sequential traversal of binary trees

Language: javassript

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[][]}* /
var levelOrder = function(root) {

    if(! root){return [];
    }
    let queue=[];
    queue.push(root);
    let res=[];
    while(queue.length){
       let arr=[];
       for(let i=0,len=queue.length; i<len; ++i){let node=queue.shift();
            arr.push(node.val);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
       }
       res.push(arr);
    }
    return res;
};
Copy the code