二叉树 - LATracy/Leetcode Wiki

Original URL: https://github.com/LATracy/Leetcode/wiki/二叉树
  1. 二叉树的前序遍历
法一:栈
def preorderTraversal(self, root: TreeNode) -> List[int]:
    if not root: return []
    stack = list()
    ans = []
    stack.append(root)
    while stack:
        curr = stack.pop()
        ans.append(curr.val)
        if curr.right: stack.append(curr.right)
        if curr.left:stack.append(curr.left)
    return ans

法二:递归
def preorderTraversal(self, root: TreeNode) -> List[int]:
    if not root: return []
    stack = []
    ans = []
    self.helper(root,ans)
    return ans
def helper(self,curr:TreeNode,ans):
    if not curr: return
    ans.append(curr.val)
    if curr.left: self.helper(curr.left,ans)
    if curr.right:self.helper(curr.right,ans)

94.二叉树的中序遍历

def inorderTraversal(self, root: TreeNode) -> List[int]:
    if not root: return []
    stack = []
    curr = root
    ans = []
    while stack or curr:
        if curr:
            stack.append(curr)
            curr = curr.left
        else:
            curr = stack.pop()
            ans.append(curr.val)
            curr = curr.right
    return ans
  1. 二叉树的后序遍历
def postorderTraversal(self, root: TreeNode) -> List[int]:
    if not root: return []
    stack = [root]
    ans = []
    while stack:
        curr = stack.pop()
        ans.append(curr.val)
        if curr.left: stack.append(curr.left)
        if curr.right: stack.append(curr.right)
    return list(reversed(ans))

102.二叉树的层序遍历

def levelOrder(self, root: TreeNode) -> List[List[int]]:
    if not root: return []
    queue = collections.deque()
    queue.append(root)
    ans = []
    while queue:
        inlist = []
        for i in range(len(queue)):
            node = queue.popleft()
            inlist.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        ans.append(inlist)   
    return ans
  1. 对称二叉树
递归:
def isSymmetric(self, root: TreeNode) -> bool:
    if not root:return True
    stack = list()
    stack.append(root.left)
    stack.append(root.right)
    while stack:
        n1 = stack.pop()
        n2 = stack.pop()
        if not n1 and not n2: continue
        elif (not n1) or (not n2) or n1.val!=n2.val: return False
        else:
            stack.append(n1.left)
            stack.append(n2.right)
            stack.append(n1.right)
            stack.append(n2.left)
    return True 

迭代:
def isSymmetric(self, root: TreeNode) -> bool:
    if not root:return True
    stack = list()
    stack.append(root.left)
    stack.append(root.right)
    while stack:
        n1 = stack.pop()
        n2 = stack.pop()
        if not n1 and not n2: continue
        elif (not n1) or (not n2) or n1.val!=n2.val: return False
        else:
            stack.append(n1.left)
            stack.append(n2.right)
            stack.append(n1.right)
            stack.append(n2.left)
    return True