Created
January 13, 2022 20:45
-
-
Save makeapp007/f1a4830f6e46a643a5597c60a85ac318 to your computer and use it in GitHub Desktop.
Leetcode 144. Binary Tree Preorder Traversal
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| recursion | |
| class Solution: | |
| def preorderTraversal(self, root: TreeNode) -> List[int]: | |
| if not root: | |
| return [] | |
| ret = [] | |
| def dfs(node): | |
| if not node: | |
| return | |
| ret.append(node.val) | |
| dfs(node.left) | |
| dfs(node.right) | |
| dfs(root) | |
| return ret | |
| Explanation: In the dfs function, If node is not null, we store its value and visit its left side, and then its right side. | |
| Optimize: | |
| class Solution: | |
| def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: | |
| if not root: return [] | |
| return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right) | |
| We can also implement it iteratively. | |
| class Solution: | |
| def preorderTraversal(self, root: TreeNode) -> List[int]: | |
| if not root: | |
| return [] | |
| stack, ret = [root], [] | |
| while stack: | |
| node = stack.pop() | |
| ret.append(node.val) | |
| if node.right: | |
| stack.append(node.right) | |
| if node.left: | |
| stack.append(node.left) | |
| return ret | |
| Explanation: | |
| Notice that the order is Node, Left, Right. We can use a stack to store the node's right child first and then store the nodes' left child. If the node has a left child, we can get that by stack.pop() | |
| This runs fast than the recursive approach |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment