Todays‘ leetcode

257. 二叉树的全部路径 - 力扣（LeetCode）
You're mostly on the right track! The helper function indeed uses recursion to explore both the left and right paths of each node in the binary tree.
When we call helper(node.left, path.copy()), we're starting to explore all the possible paths that go through the left subtree of the current node. The path.copy() is important because we want to keep the original path intact for when we later explore the right subtree. So, the exploration of the left subtree proceeds recursively, building up the path as it goes down the tree.
Similarly, when we call helper(node.right, path.copy()), we're doing the same thing but for the right subtree of the current node.
It's not exactly correct to say "at last return path" in a simple sense though. When we reach a leaf node (a node with no left and no right children), we construct a string from the path list (using -> to join the node values) and add that string representation of the path to the paths list.
As the recursive calls unwind (after exploring all possible paths from a particular node's subtrees), the path.pop() statement removes the value of the current node from the path list to backtrack and allow exploration of other paths from its parent node.
The overall goal is to build up and collect all the possible root-to-leaf path strings in the paths list, which is then returned by the binaryTreePaths function at the end. So, the helper function works in a coordinated recursive way to explore all paths and manage the path list and the collection of final paths appropriately.

1. class TreeNode:
2.     def __init__(self, val=0, left=None, right=None):
3.         self.val = val
4.         self.left = left
5.         self.right = right
8. def binaryTreePaths(root):
9.     paths = []
11.     def helper(node, path):
12.         if not node:
13.             return
14.         path.append(str(node.val))
15.         if not node.left and not node.right:
16.             paths.append("->".join(path))
17.         else:
18.             helper(node.left, path.copy())
19.             helper(node.right, path.copy())
20.         path.pop()
22.     helper(root, [])
23.     return paths

复制代码

The helper function is a crucial part of the solution for finding all root-to-leaf paths in a binary tree. Let me break down how it works step by step to make it clearer for you:
1. Function signature and initial purpose:
The helper function is defined as def helper(node, path):. Its main job is to traverse the binary tree recursively while keeping track of the current path from the root to the current node. The node parameter represents the current node being examined in the tree, and the path parameter is a list that stores the values of the nodes along the current path.
2. Base case:
The first line inside the helper function is if not node: return. This is the base case for the recursion. If the node is None, it means we've reached an empty part of the tree (either the left or right child of a node doesn't exist), and there's nothing more to explore from this point. So, we simply return and move back up the call stack.
3. Adding the current node to the path:
The line path.append(str(node.val)) adds the value of the current node to the path list. We convert the node's value to a string because later we'll join all the values in the path list with the "->" separator to form a nice string representation of the path. For example, if we have a path with node values 1, 2, and 5, we want the final path string to be "1->2->5".
4. Checking if it's a leaf node:
The condition if not node.left and not node.right: checks if the current node is a leaf node (i.e., it has no left and no right children). When we reach a leaf node, we've found a complete root-to-leaf path. So, we create a string from the path list using paths.append("->".join(path)) and add it to the paths list, which stores all the root-to-leaf paths in the tree.
5. Recursive calls for non-leaf nodes:
For non-leaf nodes (nodes that have at least one child), we make two recursive calls: helper(node.left, path.copy()) and helper(node.right, path.copy()). We use path.copy() because when we make a recursive call to explore the left subtree, we don't want the changes made to the path for the left subtree to affect the exploration of the right subtree. Each recursive call will continue the traversal down the tree from the respective child node while passing along the current path.
6. Backtracking:
The line path.pop() is used for backtracking. After we've explored all the paths starting from a particular node (both its left and right subtrees), we need to remove the value of that node from the path list. This allows us to go back up the tree and explore other possible paths from its parent node. For example, if we've explored all the paths starting from the left child of a node, we need to remove the left child's value from the path before exploring the paths starting from the right child.
Overall, the helper function uses recursion to systematically explore all possible root-to-leaf paths in the binary tree, adding each complete path to the paths list as it's found.


another way:
i always confused with recrusion,so this way ,i can make it easy ,but. ikone i will face it one day ,just make it later and later.

1. def construct_paths(root, path):
2.             if root:
3.                 path += str(root.val)
4.                 if not root.left and not root.right:  # if reach a leaf
5.                     paths.append(path)  # update paths  
6.                 else:
7.                     path += '->'  # extend the current path
8.                     construct_paths(root.left, path)
9.                     construct_paths(root.right, path)
11.         paths = []
12.         construct_paths(root, '')
13.         return paths

复制代码

404. 左叶子之和 - 力扣（LeetCode）
You've got a solid understanding of the logic! Your thoughts are in line with the recursive approach to solve this problem.

1. class TreeNode:
2.     def __init__(self, val=0, left=None, right=None):
3.         self.val = val
4.         self.left = left
5.         self.right = right
8. class Solution:
9.     def sumOfLeftLeaves(self, root):
10.         if not root:
11.             return 0
13.         sum_left_leaves = 0
15.         # Check the left subtree
16.         if root.left:
17.             # If the left child is a leaf node
18.             if not root.left.left and not root.left.right:
19.                 sum_left_leaves += root.left.val
20.             else:
21.                 # Recursively find the sum of left leaves in the left subtree
22.                 sum_left_leaves += self.sumOfLeftLeaves(root.left)
24.         # Recursively find the sum of left leaves in the right subtree
25.         sum_left_leaves += self.sumOfLeftLeaves(root.right)
27.         return sum_left_leaves
28. Here's how this code works:

复制代码

1. Base case: The if not root: statement checks if the current root node is None. If it is, we return 0 because there are no left leaves in an empty tree.
2. Processing the left subtree: When root.left exists (i.e., the current node has a left child), we then check if that left child is a leaf node. If it is (both root.left.left and root.left.right are None), we add the value of the left child (root.left.val) to the sum_left_leaves. If the left child is not a leaf node, we make a recursive call to self.sumOfLeftLeaves(root.left) to continue the search for left leaves in the left subtree.
3. Processing the right subtree: We make a recursive call to self.sumOfLeftLeaves(root.right) to search for left leaves in the right subtree. The results from the right subtree's exploration are added to the sum_left_leaves.
4. Returning the result: Finally, we return the sum_left_leaves, which is the sum of all the left leaves in the entire binary tree.

1. if root is None:
2.             return 0
3.         if root.left is None and root.right is None:
4.             return 0
5.         
6.         leftValue = self.sumOfLeftLeaves(root.left)  # 左
7.         if root.left and not root.left.left and not root.left.right:  # 左子树是左叶子的情况
8.             leftValue = root.left.val
9.             
10.         rightValue = self.sumOfLeftLeaves(root.right)  # 右
12.         sum_val = leftValue + rightValue  # 中
13.         return sum_val

复制代码

287. 寻找重复数 - 力扣（LeetCode）
it is hard to understand,why use binary search to solve.
 




免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。