Notes: middle order traversal of binary trees (three solutions - recursion, iteration, Morris)

Middle order traversal of binary trees ： Left root right
subject ：https://leetcode.cn/problems/binary-tree-inorder-traversal/

First solution （ The recursive method ）

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func inorderTraversal(root *TreeNode) []int {
    
    //  The boundary conditions 
    if root == nil{
    
        return []int{
    }
    }
    //  Left root right 
    var res []int
    if root.Left != nil{
    
        res = append(res, inorderTraversal(root.Left)...)
    }
    res = append(res, root.Val)
    if root.Right != nil{
    
        res = append(res, inorderTraversal(root.Right)...)
    }
    return res
}

The main points of 1. The boundary conditions , If the input is empty [], Need special treatment , Otherwise, null pointer exception will be reported .

Official solution （ recursive ）

The idea of recursion is the same , The difference is the processing of the result array , The official introduction of function variables . Assign a function to a variable , Then the variable becomes “ Callback function ”.

func inorderTraversal(root *TreeNode) (res []int) {
    
    var inorder func(node *TreeNode) //  Declare function variables 
    //  Define function assignment to function variable 
    inorder = func(node *TreeNode){
    
        if node == nil{
    
            return 
        }
        inorder(node.Left) //  Recursive left subtree 
        res = append(res, node.Val) 
        //  actually , In the recursion of the above left subtree, the node values are constantly added res Result set 
        //  Therefore, the value of the current node is added here ok
        inorder(node.Right) //  Recursive right subtree 
    }
    //  Actually execute the function 
    inorder(root)
    return //  here res It has been declared in the function signature , So right. res Return directly after operation  
}

Recursive solution complexity analysis ： Time O(n) Go through every node Space O(n) If the tree degenerates into a linked list , You need to store all nodes

Official solution 2（ iteration ）：

The iterative method is actually to present the stack in recursion .golang Medium stack It should be a TreeNode Array , To get out of the stack is to delete the last element （stack[len-1]) Stack is append

func inorderTraversal(root *TreeNode) (res []int) {
    
	stack := []*TreeNode{
    }
    //  In a traverse root Not empty , Or the stack is not empty 
    //（ For example, the left subtree traverses to empty , Then take out the root node in the stack , Then continue to traverse its right subtree 
    for root != nil || len(stack) > 0{
    
        //  Traverse left subtree 
        for root != nil{
    
            stack = append(stack, root)
            root = root.Left
        }
        //  here root == nil  Indicates that the left subtree has been traversed , Take the root from the stack 
        root = stack[len-1]
        // stack The last element of the stack 
        stack = stack[:len-1]
        //  take root Add the value of （ Traverse to the root ）
        res = append(res, root.Val)
        root = root.Right
    }
    return
}

Official solution 3（ Space complexity is optimized to O(1)) Morris inorder traversal

Use one predecessor（ The former ） Variable to point to the previous node of the current node .
Set the current node to x, First judgement x The left child ：

1. x No left child , First of all x Add results , then x Set as x The right child
2. x There are left children , Then we find x The last node in the subtree to be added to the result set （ The rightmost node ）,predecessor Point to the rightmost node .
   And then according to predecessor Whether there is a right child to judge ：
3. If prodecessor The right child is empty , Then the right child of this node （Right） Point to x（ Because the next one is going to traverse x 了 ）, And will x Point to the left node , Start by traversing the left subtree （prodecessor Save the root at this time ）
4. If prodecessor The right child is not empty , Then we have traversed its left subtree , Should be x node （ root ） Add result set , And then I go through the right subtree . The specific operation is ： We will x The value of is added to the result set , And will predecessor The right child of is left blank , And then visit x The right child （x=x.Right)
   take x The right child of the rightmost node of the left subtree of changes from empty to pointing x. In this way, you can walk back after traversing the left subtree x. It means that the root node is saved with a null pointer .
   This prodecessor The node is equivalent to the current node taking a left step , Then go straight to the right until you can't go any further .

func inorderTraversal(root *TreeNode) (res []int) {
    
    for root != nil{
    
        if root.Left != nil{
     // x There are left children 
            predecessor := root.Left  
            //  Because on the way, it may be because prodecessor The right child of is empty, so prodecessor Gyrus digiti x  this 
            //  At this point, there is no circulation 
            // 1.  Go straight to the right here 
            for predecessor.Right != nil && predecessor.Right != root{
    
                predecessor = predecessor.Right
            }
            // predecessor  It's the rightmost node   Start judging his right child 
            if predecessor.Right == nil{
    
                predecessor.Right = root
                root = root.Left
            } else {
    
                //  here predecessor.Right Must point to x node , Indicates that the left subtree has been traversed 
                res = append(res, root.Val) //  The root is added to the result set 
                predecessor.Right = nil //  The right of the precursor node is empty   When entering the cycle again prodecessor It's empty 
                //  Go directly to the case where there is no left subtree , See below 
                root = root.Right //  Start traversing the right subtree 
            }
        } else {
    
            //  There is no left subtree 
            res = append(res, root.Val) //  The root is added to the result set 
            root = root.Right //  Start traversing the right subtree 
        }
    }
    return
}