Binary tree problems

As mentioned above Introduction and application of tree , Let's try a few more examples in this article .

226. Flip binary tree

Their thinking ：

As we mentioned above , Encounter tree problems , Let's see if the problem can be solved directly by traversal ？

In fact, we use the method of preorder traversal , Reverse the left and right subtrees layer by layer .

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:return 
        self.traverse(root)
        return root
    
    def traverse(self, root):
        if not root:return

        tmp = root.left
        root.left = root.right
        root.right = tmp

        self.traverse(root.left)
        self.traverse(root.right) 

Can it be decomposed ？

There are two ways to decompose , Respectively corresponding to pre order traversal and subsequent traversal .

Decomposition is usually done by recursively calling the function itself , And then deal with the child nodes of each layer .

# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
    if not root:return 
	
	root.left, root.right = root.right, root.left #  Preface 
	
    self.invertTree(root.left)
    self.invertTree(root.right)
    
    return root

# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
    if not root:return 
    self.invertTree(root.left)
    self.invertTree(root.right)

    root.left, root.right = root.right, root.left #  In the following order 
    return root

The above recursive method is also DFS The embodiment of , Let's take a look BFS Methods .

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        
        if not root:return 
        queue = [root]
        while queue:
            tmp = queue.pop(0)
            tmp.left, tmp.right = tmp.right, tmp.left

            if tmp.left:
                queue.append(tmp.left)
            if tmp.right:
                queue.append(tmp.right)

        return root

116. Fill in the next right node pointer for each node

Their thinking ：

This path can also be solved directly by traversal , But pay attention ：

Like the previous question, the preorder traversal is as follows ,

The idea of dichotomy is followed here , Traverse the left and right subtrees respectively , Therefore, the lowest level of different parent nodes , The child nodes of .

That is, in the example of the topic 5 Unable to point 6.

	
	pass		#  Priority position 
	
    self.invertTree(root.left)
    self.invertTree(root.right)

We can solve this problem by adding a line of recursion .

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':

        if not root:
            return None
        
        self.traverse(root.left, root.right)
        return root

    def traverse(self, node1, node2):
        if not node1 or not node2:
            return

        node1.next = node2 #  The nodes on the left point to the nodes on the right 

        self.traverse(node1.left, node1.right)
        self.traverse(node1.right, node2.left) #  Add connections between different parent nodes 
        self.traverse(node2.left, node2.right)

114. The binary tree is expanded into a list

I hope we can flatten the binary tree into a linked list in place .

So we use the preorder traversal method to traverse directly , Constructing a linked list violates the meaning of the question .

So this problem uses the method of decomposition , Use recursion to level the linked list in place .

Specific details are as follows , You can watch it a few more times .

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """ Do not return anything, modify root in-place instead. """

        if not root:
            return
            
		
        self.flatten(root.left)
        self.flatten(root.right)

        #1. Postorder traversal position , Decomposing a problem is often a bottom-up process for dealing with subproblems 
        #  Use examples of topics , Let's take the left subtree of the root node as an example  2->3->4
        # Record the left and right subtrees of the current node 
        left = root.left # here  3  by  left, come from  （2.left->3）
        right = root.right #4  by  right,  come from  （2.right->4）

        #2. Take the left subtree as the right , Set the left subtree to  None,  Do not process the value of the right subtree just recorded  
        root.right = left #2.right->3
        root.left = None #2.left->null
		
		#3.  The original right subtree （right） Connect to the current right subtree （2.right->3）
        p = root # The current node is  2
        while(p.right is not None): # 2->3 
            p = p.right  #  If you don't traverse to the node 3, node  3  Will lose 
        p.right = right  #4
                        #2.right->3->4
		# The above is based on the root node  1  For example, the left subtree of , In recursive order , The right subtree of the root node is processed as above .