[Leetcode][python]Binary Tree Preorder Traversal/二叉树的前序遍历

港控/mmm° 2022-06-11 08:17 137阅读 0赞

## 题目大意 ##

二叉树前序遍历  
**挑战**：迭代解题

## 解题思路 ##

递归简单

迭代思路：见下方代码前

1
    
    　　　　　　　/     \
    
    　　　　　 2         3
    
    　　　 /     \    /    \
    
    　　  4       5  6      7

## 代码 ##

### 递归 ###

class Solution(object):
        def _preorderTraversal(self, root, result):
            if root:
                result.append(root.val)
                self._preorderTraversal(root.left, result)
                self._preorderTraversal(root.right, result)
        def preorderTraversal(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            if root == None:
                return []
            result = []
            self._preorderTraversal(root, result)
            return result

### 迭代 ###

1.根节点入栈  
2.取出节点，值加入结果，然后先加右，后加左。  
3.重复2

**注意：就算节点没有孩子，其指向孩子的指针（node.left）是None，不会报错**

**但是如果取值node.left.val，则会报错。所以最好是像要判断一下if node.left/right，因为这样栈中就不会有None，多浪费了时间。**

while stack:
        node = stack.pop()
        if node:
            ret.append(node.val)
            stack.append(node.right)
            stack.append(node.left)
    
    <precompiled.treenode.TreeNode object at 0x7f19ec21fc90>
    None
    None

class Solution(object):
        def preorderTraversal(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            ret = []
            stack = [root]
            while stack:
                node = stack.pop()
                if node:
                    ret.append(node.val)
                    if node.right:
                        stack.append(node.right)
                    if node.left:
                        stack.append(node.left)
            return ret

## 总结 ##