This paper mainly describes the common methods used to solve binary tree type problems in Leecode, and each method is analyzed through leetCode sample problems. You are welcome to correct me.
First, use recursive traversal to solve the problem
The key point of binary tree recursive solution is to consider the relationship between the root node, the left subtree and the right subnumber. The rest of the work is handed over to traversal processing.
if root == None:return None
# Preorder traversal: do_something
traverseTree(root.left)
# in order traversal: do_something
traverseTree(root.right)
# Post-order traversal: do_something
Copy the codeTopic 1: Binary tree depth (Leetcode)
The depth of the tree = Max (the depth of the left subtree, the depth of the right subtree)+1, using the frame to get the following code:
def maxDepth(self, root) :
""" :type root: TreeNode :rtype: int """
if not root:
return 0
Find the left subtree depth
ldepth = self.maxDepth(root.left)
Find the depth of the right subtree
rdepth = self.maxDepth(root.right)
# Tree depth
depth = max(ldepth,rdepth) + 1
return depth
Copy the codeTopic 2: Diameter of binary tree (Leetcode)
Any path with a diameter must have a node. Divide the path into left and right subtrees (left and right subtrees can be empty). For the subtree with this node as the root node, the length of the tree diameter path can be transformed into the depth of the tree, as follows: The diameter of the tree = the depth of the left subtree + the depth of the right subtree. So find the left and right subtree depth of all nodes, get the diameter of all subtrees, the largest is the diameter of the tree. As shown in the figure below:
The depth of the left subtree of the selected node is 3, and the depth of the right subtree of the selected node is also 3, so the diameter of the selected subtree is 3+3=6.
def diameterOfBinaryTree(self, root) :
""" :type root: TreeNode :rtype: int """
self.ans = 0
def depth(node) :
if not node:
return 0
L = depth(node.left)
R = depth(node.right)
self.ans = max(self.ans,L+R)
return max(L,R)+1
depth(root)
return self.ans
Copy the code1. Special Scenario – Two nodes are traversed at the same time
Two nodes traversal is mainly aimed at the problem that two nodes need to be processed at the same time. The focus is to think about what operations need to be done between the two nodes and how to traverse the next two child nodes. The basic framework is as follows:
if root == None:
return True
return self.helper(root.left,root.right)
def helper(self,node1,node2) :
ifReach the boundary conditions:return
Do_something () do_something()Self. helper(node1. Child node, node2. Child node)Copy the codeTopic 3: Symmetric Binary trees (Leetcode)
Train of thought: the two nodes at the same time through sometimes is one of the important magic weapon, some special problems such as symmetric binary tree, need to determine whether each layer of the symmetric node values are consistent, obviously need to traverse the two nodes at the same time, so in function signatures, you need to set up two into arguments and recursive at the same time, the way certain relations of two nodes can be all traversal.
def isSymmetric(self, root) :
""" :type root: TreeNode :rtype: bool """
if root == None:
return True
return self.helper(root.left,root.right)
def helper(self,node1,node2) :
If two nodes are non-empty and have the same value, then recursively determine whether the children of the two nodes are the same
ifnode1 ! =None andnode2 ! =None and node1.val == node2.val:
return self.helper(node1.left,node2.right) and self.helper(node1.right,node2.left)
# Boundary condition that returns True if both nodes are null
if node1 == None and node2 == None:
return True
return False
Copy the codeTitle 4: Fill the next right node pointer (Leetcode) for each node
The problem can be solved through recursive traversal or hierarchical traversal.
Idea: This analysis iterates recursively. Based on the observation that two nodes of the same level need to be associated in turn, we can consider the special scenario of traversal – two nodes traversing at the same time. Build the helper function connectTwoNodes, which takes in two nodes and concatenates them with the boundary condition that the first node is null. All nodes can be concatenated as required by recursive calls.
def connect(self, root) :
""" :type root: Node :rtype: Node """
if root == None:
return root
root.next = None
self.connectTwoNodes(root.left,root.right)
return root
# Connect two nodes
def connectTwoNodes(self,firstNode,secondNode) :
The child node is null and returns directly
if firstNode == None:
return None
firstNode.next = secondNode
secondNode.next = None
Connect the left child of the first node to the right child of the first node
self.connectTwoNodes(firstNode.left,firstNode.right)
Connect the right child of the first node to the left child of the second node
self.connectTwoNodes(firstNode.right,secondNode.left)
Connect the left child of the second node to the right child of the second node
self.connectTwoNodes(secondNode.left,secondNode.right)
return None
Copy the code2. Special scenarios – Build binary trees
The addition and deletion of binary tree will affect the left and right Pointers of binary tree nodes. Therefore, compared with traversal, we need to pay attention to the assignment of the left and right Pointers of binary tree nodes.
Topic 5: Constructing binary trees (LeetCode) from preordered and in-order Traversal sequences
Idea: according to the nature of the traversal can that can be determined by the preorder traversal of binary tree root node, the root node of the binary tree and then set the sequence traversal divided the left part of the left subtree, the right side of building right subtree, finally through the entire tree recursive binary tree to build complete, attention needs to be in the process of building around the root node pointer assignment.
def buildTree(self, preorder, inorder) :
""" :type preorder: List[int] :type inorder: List[int] :rtype: TreeNode """
if len(preorder) == 0:
return None
# Fetch the root node of the tree from the preorder traversal sequence
root = TreeNode(preorder[0])
Divide the left subtree and right subtree according to the position of the root node in the in order traversal
index = inorder.index(preorder[0])
# Recursively build the left subtree, with node Pointers assigned
root.left = self.buildTree(preorder[1:index+1],inorder[0:index])
# Recursively construct the right subtree with node Pointers assigned
root.right = self.buildTree(preorder[index+1:],inorder[index+1:)return root
Copy the codeSecond, use width first traversal to solve the problem
Let’s take a look at the width first search (BFS) traversal as shown below:
BFS is usually implemented using queue data structures. The framework is as follows:
if root == None:return None
# Implement node FIFO using queue
lst = []
lst.append(root)
whilelst ! = []: node = lst.pop(0)
Do_something # traversal
ifnode.left ! =None:
lst.append(node.left)
ifnode.right ! =None:
lst.append(node.right)
Copy the codeBut usually we need to know the hierarchical relationship of each node in the process of solving problems, and BFS cannot distinguish the hierarchical relationship of each node. Therefore, it is necessary to add a counter in the BFS traversal process to record the number of nodes at each level, thus forming the level traversal. The framework is as follows:
if root == None:return None
# Implement node FIFO using queue
lst = []
lst.append(root)
whilelst ! = [] :# Calculate the number of nodes in a new row every time it arrives
n = len(lst)
for i in range(n):
node = lst.pop(0)
Do_something # traversal
ifnode.left ! =None:
lst.append(node.left)
ifnode.right ! =None:
lst.append(node.right)
Copy the codeTopic 6: Sequential Traversal of binary trees (Leetcode)
Train of thought: direct upper level traversal framework can
def levelOrder(self, root) :
""" :type root: TreeNode :rtype: List[List[int]] """
if root == None:
return []
lst = []
ans = []
lst.append(root)
whilelst ! = []: n =len(lst)
# Create a new list for each line
ans.append([])
for i in range(n):
node = lst.pop(0)
ans[-1].append(node.val)
ifnode.left ! =None:
lst.append(node.left)
ifnode.right ! =None:
lst.append(node.right)
return ans
Copy the codeTitle 7: Fill the next right node pointer (Leetcode) for each node
In the process of traversal, the nodes of the same layer are associated with each other. It should be noted that except the last node in each row, the remaining nodes are associated with the nodes of the next row 2-3,4-5,5-6,6-7. The following solution also solves the Leetcode-117 problem “Fill the next right node pointer II for each node”. This problem also has a recursive traversal solution, see problem 4.
def connect(self, root) :
""" :type root: Node :rtype: Node """
if root == None:
return None
lst = []
lst.append(root)
whilelst ! = []: n =len(lst)
for i in range(n):
node = lst.pop(0)
ifnode.left ! =None:
lst.append(node.left)
ifnode.right ! =None:
lst.append(node.right)
If this is the last node in the row, the next pointer is not required
if i == n-1:
continue
# Concatenate the next node in the same row
node.next = lst[0]
return root
Copy the code