“This is the 7th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

The title

Give you the root node of the binary tree, root, and return the preceding ** traversal of its node value.

 

Example 1:

Recursive solution:

We pass the root node root and initialize the result array res=[], res.push(root.val) if root is not empty, then recursively call itself and pass root.left. After processing the left node, the recursively call processes the right node root.right.

Recursive solution code:

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root,res=[]) {
    if(root == null){
        return res;
    } 

    res.push(root.val)
    preorderTraversal(root.left,res)
    preorderTraversal(root.right,res)
    return res
};
Copy the code

Iterative solution:

Recursive method, equivalent to the system to maintain a stack, each recursive call, the rest of the code logic stored in the stack, such as recursion to the last layer, began to bounce out, and then layer by layer to execute the remaining logic code in the stack.

Iteration method, then, you need to maintain a stack, preorder traversal of binary tree, is the root of traversal sequence, so every time we traverse the root node, in turn, left right node pressure into the stack, and then removed from the stack left node, as a new “root”, press the new nodes right, left again into the stack and so on.

Iterative solution code:

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root,res=[]) {
    if(root == null){
        return res;
    } 

    let stack = [];
    stack.push(root);
    while(stack.length>0){
        let node = stack[stack.length - 1];
        stack.pop();
        res.push(node.val);
        if(node.right){
            stack.push(node.right);
        }
        if(node.left){
            stack.push(node.left);
        }
    }
    return res
};
Copy the code

Morris, a solution:

Ideas:

Set two Pointers, P1 and p2, with P1 pointing to the current traversal node and P2 pointing to the rightmost child node of p1’s left leaf. Normally, untreated P2 nodes should be P2! =null &&p2. right ==null, or p2 ==null

P2 can be in the following three states:

  1. If p2! P2. right==null &&p2. right==null, the object is first called, and the return pointer has not been built, so let p2.right=p1, and print the value of p1. Loop through the operation to build a return pointer on all right-trailing nodes on the left.

  2. If p2 == null, it indicates that P1 has reached the end of the left node of its left leaf. Then, print the value of P1 and let P1 go to the right, that is, P1 = p1.right. Since the current node of P1 has built a return path pointer in the previous step, it can normally return to the root node of the root node of the tree where it is.

  3. If p2! == null && p2.right ! Right == null and p1 is at the root of the tree where P2 is located. This node was printed at the beginning of the tree. So instead of printing this time, p1 is going to keep going to the right, p1 is equal to right.

Repeat the above operations to complete the traversal.

So in general, there are only three states of P2, and the whole traversal is going around the state of P2.

I’m going to fill in an animation breakdown later.

The code implementation is as follows:

/** * @param {TreeNode} root * @return {number[]} */ var preorderTraversal = function(root,res=[]) { if(root == null){ return res; } let p1 = root; let p2 = null; while(p1 ! = null){ p2 = p1.left; if(p2 ! = null){ while(p2.right ! = null && p2.right ! = p1){ p2 = p2.right; } if(p2.right == null){ res.push(p1.val); p2.right = p1; p1 = p1.left; continue; } p2.right = null; }else{ res.push(p1.val); } p1 = p1.right; } return res; };Copy the code