Leetcode recursion

q21 Merge two ordered lists

Subject portal

Answer key

Recursive and iterative methods can be used to solve , Both methods are relatively simple .

recursive ：

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    
	if l1 == nil {
    
		return l2
	} else if l2 == nil {
    
		return l1
	} else if l1.Val < l2.Val {
    
		l1.Next = mergeTwoLists(l1.Next, l2)
		return l1
	} else {
    
		l2.Next = mergeTwoLists(l1, l2.Next)
		return l2
	}
}

iteration ：

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    
	L := &ListNode{
    }
	curr := L
	var next *ListNode
	for l1 != nil && l2 != nil {
    
		if l1.Val < l2.Val {
    
			next = l1.Next
			curr.Next = l1
			l1.Next = nil
			l1 = next
		} else {
    
			next = l2.Next
			curr.Next = l2
			l2.Next = nil
			l2 = next
		}
		curr = curr.Next
	}
	if l1 != nil {
    
		curr.Next = l1
	}
	if l2 != nil {
    
		curr.Next = l2
	}
	return L.Next

q101 Symmetric binary tree

Subject portal

Answer key

This problem is solved by recursion , First, judge the boundary conditions , If both are nil, Just go back to real , If not at the same time nil, Return to leave , Finally, judge p and q Are the values of the nodes equal , And recursively determine whether their child nodes are equal .

func isSymmetric(root *TreeNode) bool {
    
	var check func(p, q *TreeNode) bool
	check = func(p, q *TreeNode) bool {
    
		if p == nil && q == nil {
    
			return true
		}
		if p == nil || q == nil {
    
			return false
		}
		return p.Val == q.Val && check(p.Left, q.Right) && check(p.Right, q.Left)
	}
	return check(root, root)
}

q104 The maximum depth of a binary tree

Subject portal

Answer key

Solve it recursively , Define a recursive function , First judgement L Is it right? nil, If it is nil Go straight back to 0; otherwise , Recursively get the height of the left and right subtrees , Then judge the height of the left and right subtrees , Return to the high one +1.

func maxDepth(root *TreeNode) int {
    
	var Count func(L *TreeNode) int
	Count = func(L *TreeNode) int {
    
		if L == nil {
    
			return 0
		} else {
    
			lChild := Count(L.Left)
			rChild := Count(L.Right)
			if lChild > rChild {
    
				return lChild + 1
			} else {
    
				return rChild + 1
			}
		}
	}
	return Count(root)
}

q226 Flip binary tree

Subject portal

Answer key

Or use the idea of recursion , Let's start at the root , Recursively traverse the tree , And flip from the leaf node , Then turn up step by step , Last flip root The left and right subtrees of nodes .
The flip strategy is like this , When traversing to a node , First, judge whether the node is nil, If it's straight back nil, Otherwise, first recursively flip the left subtree , Then recursively flip the right subtree , Finally, exchange the left and right subtrees .

func invertTree(root *TreeNode) *TreeNode {
    
	if root == nil {
    
		return nil
	} else {
    
		left := invertTree(root.Left)
		right := invertTree(root.Right)
		root.Left = right
		root.Right = left
	}
	return root
}

q236 The nearest common ancestor of a binary tree

Subject portal

Answer key

There are three situations ：

1. root by p,q One of them , At this time, the common ancestor is root
2. p and q Respectively in root On the left and right subtrees of , This public group is also root
3. p and q Only on the left or right subtree , At this time, you need to recursively traverse the left subtree or the right subtree to find

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    
	if root == nil {
    
		return nil
	}
	// root by p or q One of them 
	if root == p || root == q {
    
		return root
	}
	//  Recursive traversal of left subtree and right subtree 
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	//  If they are in the left and right subtrees , The common ancestor is root
	if left != nil && right != nil {
    
		return root
		//  Are distributed in the left subtree 
	} else if left != nil {
    
		return left
		//  Are distributed in the right subtree 
	} else {
    
		return right
	}
}

Code if p,q All of them are distributed on the left subtree or the right subtree and return directly left or right, Can we guarantee that it is the nearest public ancestor at this time ？ It can , Because after recursive traversal , Final return It starts from the leaf node return Of .