144. 二叉树的前序遍历

一、144. 二叉树的前序遍历

1.1、题目描述

1.2、题解

1.2.1、递归： 根节点->左子树->右子树

class Solution:
    def __init__(self) -> None:
        self.ans = []
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root : return []
        self.ans.append(root.val)
        if root.left:
            self.preorderTraversal(root.left)
        if root.right:
            self.preorderTraversal(root.right)
        return self.ans 

1.2.2、栈+迭代

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root : return []
        ans = []
        _stack = [root]
        
        while _stack:
            # 弹出栈顶元素
            curNode = _stack.pop()
            ans.append(curNode.val)

            # 先入右节点
            if curNode.right:
                _stack.append(curNode.right)

            if curNode.left:
                _stack.append(curNode.left)
        return ans 

1.2.3、Morris遍历

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        node, output = root, []
        while node:  
            if not node.left: 
                output.append(node.val)
                node = node.right 
            else: 
                predecessor = node.left 

                while predecessor.right and predecessor.right is not node: 
                    predecessor = predecessor.right 

                if not predecessor.right:
                    output.append(node.val)
                    predecessor.right = node  
                    node = node.left  
                else:
                    predecessor.right = None
                    node = node.right         

        return output