If the link in the text is invalid, please visit the original text: studies/tree recursion skills imhuay/studies
- foreword
- Recursive tricks for postorder traversal
- Information passing in preorder traversal
- More related questions
- References
foreword
- The three traversal methods of binary tree (preorder, inorder, postorder) represent three typical recursive scenarios ;
def dfs(node): if node is None: return ... # prologue dfs(node.left) ... # Intermediate sequence dfs(node.right) ... # post-order - The main difference between these three traversal methods is that when traversing to the current node, the positions of the known nodes are different. Take the root node as an example:
- When the preorder traversal reaches the root node, other nodes are unknown;
- When the in-order traversal reaches the root node, the entire left subtree has been traversed;
- When the post-order traversal reaches the root node, all child nodes have been traversed;
- visible,
- Preorder traversal is top-down recursion; if the current node needs the information of the parent node, preorder traversal is used;
- Post-order traversal is bottom-up recursion; if the current node needs information about child nodes, post-order traversal is used;
- In-order traversal is special, and it can be considered as unique to binary trees. For example, for a multi-fork tree, in-order traversal is out of the question, so in-order traversal is used in situations that take advantage of the unique properties of binary trees, such as binary search trees. ;
- One of the keys to our use of recursion is that we hope to decompose the problem into sub-problems and then solve them step by step,
- This is very consistent with the way of post-order traversal, that is, from the solution of the subtree, the global solution is recursively, so the problem of post-order traversal is the most;
- At this time, this recursion on the tree can be regarded as a special dynamic programming, that is, the tree dp;
- The technique introduced in this article is simply how to structure the solution of these sub-problems. This method can be used for all problems that require bottom-up recursion;
Recursive tricks for postorder traversal
Bottom-up recursion tricks, tree dp, etc.
- Note the dfs(x) template as follows:
from dataclasses import dataclass @dataclass class Info: ... # default def dfs(x) -> Info: if x is None: return Info() l_info = dfs(x.left) r_info = dfs(x.right) x_info = get_from(l_info, r_info) return x_info - Consider what information needs to be obtained from the left and right subtrees to calculate the answer of the current node, and assume that it is known, note l_info and r_info;
- Use l_info and r_info to construct the information x_info that the current node should return;
- Pay attention to the information returned by the empty tree, which is the default value of Info;
- For readability, it is recommended to use a structure (recommended to use dataclass in python) to store the required information;
- Further, the final generated x_info may not all be related to x. In this case, it is necessary to discuss the answer related to x and the answer not related to x, and take the optimal solution (see examples 3 and 4 for details);
Example 1: Height of binary tree
104. Maximum depth of binary tree - LeetCode
- The height of the binary tree x is equal to the greater of the heights of the left and right subtrees + 1;
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
def dfs(x):
if x is None: return 0
l, r = dfs(x.left), dfs(x.right)
return max(l, r) + 1
return dfs(root)
This question is relatively simple, so the template is simplified;
Example 2: Determine whether it is a balanced binary tree/search binary tree/complete binary tree
98. Verify Binary Search Tree - LeetCode
110. Balanced Binary Tree - LeetCode
958. Completeness Test of Binary Tree - LeetCode
- Search binary tree: for each node, its value is greater than the maximum value of the left subtree and less than the minimum value of the right subtree;
- Balanced binary tree: For each node, the height difference between its left and right subtrees is <= 1;
- Complete binary tree, here are two judgment conditions:
- Condition 1:
- The left and right subtrees are full binary trees and have the same height, that is, they are full binary trees;
- The left and right subtrees are full binary trees, and the height of the left subtree is +1;
- The left subtree is a full binary tree, and the right subtree is a complete binary tree with the same height;
- The left subtree is a complete binary tree, the right subtree is a full binary tree, and the height of the left subtree is +1;
Full binary tree: The height of the left and right subtrees is the same, and both are full binary trees;
- Condition 2, the method requires preorder traversal for preprocessing (see the next section for details: Information passing in preorder traversal):
- Note that the root node id is 1; if the id of the parent node is i, then its left and right child nodes are 2*i and 2*i+1 respectively;
- If it is a complete binary tree, max_id == n, where n is the total number of nodes;
- Condition 1:
- The following is the combined implementation
class Solution:
def isXxxTree(self, root: TreeNode) -> bool:
from dataclasses import dataclass
@dataclass
class Info:
height: int = 0 # height of tree
max_val: int = float('-inf') # maximum value
min_val: int = float('inf') # minimum
is_balance: bool = True # Whether to balance the binary tree
is_search: bool = True # whether to search the binary tree
is_full: bool = True # Is the binary tree full?
is_complete: bool = True # Is it a complete binary tree?
def dfs(x):
if not x: return Info()
l, r = dfs(x.left), dfs(x.right)
# Use the info of the left and right subtrees to construct the info of the current node
height = max(l.height, r.height) + 1
max_val = max(x.val, l.max_val, r.max_val)
min_val = min(x.val, l.min_val, r.min_val)
is_balance = l.is_balance and r.is_balance and abs(l.height - r.height) <= 1
is_search = l.is_search and r.is_search and x.val > l.max_val and x.val < r.min_val
is_full = l.is_full and r.is_full and l.height == r.height
is_complete = is_full \
or l.is_full and r.is_full and l.height - 1 == r.height \
or l.is_full and r.is_complete and l.height == r.height \
or l.is_complete and r.is_full and l.height - 1 == r.height
return Info(height, max_val, min_val, is_balance, is_search, is_full, is_complete)
return dfs(root).xxx # Determine the return value based on the specific problem
Example 3: Maximum path sum in binary tree
124. Maximum Path Sum in Binary Tree - LeetCode
- There are two cases according to the maximum path and whether it passes through the x node;
- If it does not go through the x node, then the maximum path sum in x is equal to the larger of the maximum path sums in the left and right subtrees;
- If it passes through the x node, then the maximum path sum of x is equal to the sum of the maximum paths that the left and right subtrees can provide, plus the value of the current node;
- Take the larger of the two;
- To sum up, the information to be recorded includes the maximum path that the current node can provide, and the current maximum path;
- The so-called "maximum path that the current node can provide", that is, the maximum value that can be obtained from the node without backtracking; assuming that the path that each node can provide is 1, then the maximum path is the height of the tree;
- Since node values have negative numbers, this is an error-prone point (see code for details);
- As can be seen from this question, templates do not solve problems, but only reduce thinking outside the problem, that is, how to convert ideas into code.
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
from dataclasses import dataclass
@dataclass
class Info:
# Error-prone point: because there are negative values, so initialize to negative infinity (minimum is -1000)
h: int = -1001 # The maximum path that the current node can provide
s: int = -1001 # Maximum path under the current node
def dfs(x):
if not x: return Info()
l, r = dfs(x.left), dfs(x.right)
# Use the information of the left and right subtrees to calculate the information of the current node
h = x.val + max(l.h, r.h, 0) # Error-prone point: If the maximum path that the left and right subtrees can provide is a negative number, it should be discarded directly
s_through_x = x.val + max(l.h, 0) + max(r.h, 0) # Error prone: same as above
# Because both h and s_through_x are related to the current node, they must contain the current node
s = max(l.s, r.s, s_through_x) # But the final result does not necessarily contain x, and the optimal solution needs to be taken
return Info(h, s)
return dfs(root).s
Example 4: Robbery III
- Tree-shaped dp, discuss whether to rob the current node in two cases;
class Solution:
def rob(self, root: TreeNode) -> int:
from functools import lru_cache
@lru_cache
def dfs(x):
# Empty node, no grab
if not x: return 0
# Leaf node, must grab
if not x.left and not x.right: return x.val
# Do not grab the current node, grab the left and right child nodes
r1 = dfs(x.left) + dfs(x.right)
# Grab the current node, skip left and right child nodes, grab child nodes of child nodes
r2 = x.val
if x.left: # non-empty judgment
r2 += dfs(x.left.left) + dfs(x.left.right)
if x.right: # non-empty judgment
r2 += dfs(x.right.left) + dfs(x.right.right)
return max(r1, r2)
return dfs(root)
Information passing in preorder traversal
- In the post-order traversal, it is natural for the parent node to obtain the information of the child node, and the recursive result can be directly received in the function body;
- In the preorder traversal, if the child node wants to obtain the information of the parent node, it cannot do so. The general method is to pass it through parameters;
from dataclasses import dataclass @dataclass class Info: ... # default def dfs(x, f_info) -> Info: if x is None: return Info() f_info = process(f_info) # Preprocessing with parent node information l_info = dfs(x.left, f_info) r_info = dfs(x.right, f_info) x_info = get_from(l_info, r_info) return x_info
Example: Determining a Complete Binary Tree
958. Completeness Test of Binary Tree - LeetCode
- Ideas:
- Note that the root node id is 1; if the id of the parent node is i, then its left and right child nodes are 2*i and 2*i+1 respectively;
- If it is a complete binary tree, max_id == total_cnt, where total_cnt is the total number of nodes;
- Here, the id of the child node needs to be calculated by the id of the parent node;
class Solution:
def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
self.total_cnt = 0
self.max_id = 0
def dfs(x, node_id):
if not x: return
self.total_cnt += 1
self.max_id = max(self.max_id, node_id)
dfs(x.left, node_id * 2)
dfs(x.right, node_id * 2 + 1)
dfs(root, 1)
return self.total_cnt == self.max_id
Example: Path Sum
- Problem brief:
- Determine whether there is a path from the root node to the leaf node in the tree and equal to targetSum;
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root: return False
self.ret = False
def dfs(x, s):
if self.ret or not x:
return
s += x.val
if x.left is None and x.right is None:
self.ret = s == targetSum
return
dfs(x.left, s)
dfs(x.right, s)
s -= x.val # backtracking
dfs(root, 0)
return self.ret
More related questions
algorithms/tree recursion