Notes: binary tree pruning (recursion, iteration)

subject

The finger of the sword Offer II 047. Two fork tree pruning

First solution （ recursive ）

The first reaction to this problem is recursion , It's a relatively simple solution to violence .
When the left subtree is empty and the right subtree is empty and its value is 0 when , Delete the node （ The way to delete is to return nil）

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func pruneTree(root *TreeNode) *TreeNode {
    
    if root == nil{
    
        return nil
    }
    // Left and right 
    root.Left = pruneTree(root.Left)
    root.Right = pruneTree(root.Right)
    if root.Left == nil && root.Right == nil && root.Val == 0{
    
        return nil
    }
    return root
}

Unexpectedly, the official did not give any other solution . Then use explicit stack to realize it .

Reinterpretation ： Construction stack

Note that after traversing the left subtree of a node , We will traverse its right subtree , At this point, we need to mark this node. We have visited the left subtree , Otherwise, the right subtree will be accessed repeatedly .

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func pruneTree(node *TreeNode) *TreeNode {
    
    //  Build a stack 
    stack := []*TreeNode{
    } //  The pointer to the node is saved here instead of itself 
    visited := new(TreeNode) //  Prevent unlimited access to the right subtree 
    root := node
    for root != nil || len(stack)> 0{
    
        //  First traverse the left 
        for root != nil{
    
            //  Root stack 
            stack = append(stack, root)
            root = root.Left
        }
        // fmt.Println(root.Val)
        //  here root It's empty 
        //  Left traversal finished , Take the root from the stack , Traversing its right subtree 
        if len(stack) > 0{
    
            // Remove the root 
            root = stack[len(stack) - 1]
            // Try traversing right   Jump back to the beginning of the loop 
            if root.Right != nil && visited != root.Right{
     //  Notice here is root.right Have you ever been interviewed   If you have visited, don't recycle . Don't write as root
                root = root.Right
            } else {
    
                //  No right , Just get out of the stack 
                stack = stack[:len(stack)-1]
                // Notice that there is a stack here , So we must judge whether the stack is empty later   There must be judgment root.right Is it empty 
                // Otherwise, the subtree will be killed 1 The node of （ It may be because visited Instead of entering if  That is, you have visited   But not necessarily empty 
                if root.Val == 0 && root.Left == nil &&root.Right == nil{
    
                    //  Find its parent node from the stack , Will point to root The pointer of is set to null 
                    if len(stack) >0{
    
                        father := stack[len(stack)-1]
                        if father.Left == root{
    
                            father.Left = nil
                        } else if father.Right == root{
    
                            father.Right = nil
                        }
                    } else {
    
                        //  There is no stack , It indicates that the last node has been out of the stack , Left and right root traversal ends , And this node should be empty 
                        return nil
                    }
                }
                // The left and right roots are traversed 
                visited = root //  He doesn't need to traverse anymore , Record this node 
                root = nil
            }
        }
    }
    return node
}