Leetcode 144– Binary tree traversal — Python

【 topic description 】

【 原 文 】

[Method 1 recursion] Use recursive way to complete the preorder traversal, simple and conventional, not much verbose, directly on the code

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        res=[]
        if not root:return res
        self.dfs(root,res)
        return res
        
    def dfs(self,root,res):
        if root:res.append(root.val)
        if root.left:self.dfs(root.left,res)
        if root.right:self.dfs(root.right,res)
Copy the code

[Method 2: Using stack iteratively]

In Python, the stack is actually implemented using the list data structure. The append of the list corresponds to the loading of the stack, and the POP corresponds to the unloading of the stack. Stack traversal is done by popping the top element on the stack, putting it on the right node, and then putting it on the left node. In a loop, as long as the stack is not empty, the loop continues.

Why is the right node pushed first and the left node pushed last?

So that the left node is always above the right node in the stack, and when you do that, the left node is always ahead of the right node, and the first step is to visit the root node, then visit the left node, then visit the right node, and that’s true for any subtree.

In the code

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        res=[]
        stack=[]
        if not root:return res
        stack.append(root)
        whilelen(stack)! =0: top=stack.pop() res.append(top.val)if(top.right):stack.append(top.right)
            if(top.left):stack.append(top.left)
        return res
Copy the code