二叉树的前序遍历

Leetcode Link: 144. 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)

题目

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

解法一

思路：递归求解。对递归序进行操作。可以思考利用全局变量怎么操作，利用局部变量怎么操作

题解： 不使用全局变量的话，需要汇总子树的信息进行操作，在汇总的时候考虑顺序

 
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def recur(cur):
            if not cur:
                return []
            node_list = [cur.val]
 
            left = recur(cur.left)
            right = recur(cur.right)
 
            node_list.extend(left)
            node_list.extend(right)
            return node_list
        
        if not root:
            return []
        else:
            return recur(root)

如果使用全局变量话，可能会稍微好理解一点，跟左成云课上讲的一样，在固定的位置进行操作即可（这个方法整体上都不如上一个方法）

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return [] 
        self.node_list = []
        self.recur(root)
        return self.node_list
 
    def recur(self, cur):
            if not cur:
                return 
            self.node_list.append(cur.val)
            self.recur(cur.left)
            self.recur(cur.right)

解法二

先序遍历_

创建一个栈，首先把根节点放进去，然后每次：

1. 从栈中弹出一个节点 cur
2. 打印（处理）该节点 cur
3. 把 cur 的右孩子压到栈里去，再把 cur 的左孩子压到栈里去
4. 重复 1-3 步

建议画图体会一下

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        stack = []
        stack.append(root)
        output = []
        while(len(stack)>0):
            cur = stack.pop()
            output.append(cur.val)
            if cur.right: stack.append(cur.right)
            if cur.left: stack.append(cur.left)
        return output

指向原始笔记的链接

解法三

思路： todo mioors 遍历

题解：

启发和联系