1. Preorder traversal

For the foreorder traversal of binary tree, we only need to judge whether the left and right subtrees exist, and then leave the rest to the iterative equation

var preorderTraversal = function(root){
    let res = []
    if(! root)return res;
    var order = function(node) {// Preorder recursive equation
        res.push(val);
        if(node.left){
            order(order.left)
        }
        if(node.right) {
            order(order.right)
        }
     }
     order(root)
     return res
}
Copy the code

The only difference of the pre-order traversal of the n-fork tree is that the n-fork tree is a whole children node, which cannot be directly added into the resulting recursive equation. Instead, the child nodes of each child should be taken out and recursed

var preorder = function(root){
    let inn = []
    if(! root)return inn;
    var order = function(node) {
        inn.push(node.val);
        if(node.children){
            for(let i =0; i<node.children.length; i++) { order(node.children[i]) } } } order(root)return inn
}
Copy the code

2. Middle-order traversal

Each node has three distinct dwell phases: 1, 2 before recursing its left subtree, 2 after recursing its left subtree, 3 before recursing its right subtree, and 3 after recursing its right subtree

const inorderTraversal = function(root) {
      const inn = [];
      const inorder = (root) => {
            if (root == null) {
                  return;
            }
      inorder(root.left);
      inn.push(root.val);
      inorder(root.right);
      };
      inorder(root);
      return inn;
};
Copy the code

3. Post-order traversal

Recursion: Recursion itself is the principle of last-in-first-out stack, through recursion from the last result saved to the array, to achieve the reverse order push to insert the array

var reversePrint = function (head) {
    let nums = []
    const visitor = function (head) {
        if(head ! = =null) {
            visitor(head.next)
            nums.push(head.val)
        }
    };
    visitor(head)
    return nums
}
Copy the code

Finally, three elements of recursion

1, confirm the arguments and return values of the recursive function:

Make sure that the parameters need to be processed in the recursive process, add this parameter to each recursive function, and specify the return value of each recursive function and the return type of the recursive function

2. Confirm termination conditions:

When the recursive algorithm is running after writing, the error of stack overflow is often encountered. Just because the termination condition is not written or the termination condition is wrong, the operating system also has a stack structure to store the information of each layer of recursion. If the recursion is not terminated, the memory stack of the operating system will overflow inevitably

3. Verify the logical level of a single level recursion:

Identifying the information that needs to be processed for each level of recursion and then calling itself repeatedly is the process that implements recursion