Golang Morris Traversal (using constant space) and iterative solution (using stack)


  • 0

    This is a variation of the in-order version.
    This algorithm is difficult to explain in just a text for me, it'd be better to see the video on the link above.

    func preorderTraversal(root *TreeNode) []int {
    	res := []int{}
    	if root == nil {
    		return res
    	}
    
    	cur := root
    	for cur != nil {
    		if cur.Left == nil {
    			res = append(res, cur.Val)
    			cur = cur.Right
    			continue
    		}
    
    		next := cur.Left
    		visited := false
    		for next.Right != nil {
    			if next.Right == cur {
    				next.Right = nil
    				cur = cur.Right
    				
    				visited = true
    				break
    			}
    			next = next.Right
    		}
    
    		if !visited {
    			next.Right = cur
    			res = append(res, cur.Val)
    			cur = cur.Left
    		}
    	}
    	return res
    }
    

    Using stack, we can solve this more simply but requires O(N) space complexity.

    func preorderTraversal(root *TreeNode) []int {
    	res := []int{}
    	if root == nil {
    		return res
    	}
    
    	stack := []*TreeNode{}
    	cur := root
    	for {
    		res = append(res, cur.Val)
    
    		if cur.Left != nil {
    			if cur.Right != nil {
    				stack = append(stack, cur.Right)
    			}
    			cur = cur.Left
    			continue
    		}
    
    		if cur.Right != nil {
    			cur = cur.Right
    			continue
    		}
    
    		if len(stack) == 0 {
    			break
    		}
    		cur = stack[len(stack)-1]
    		stack = stack[:len(stack)-1]
    	}
    
    	return res
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.