589. N叉树的前序遍历 - Easy.md

Description

给定一个 N 叉树，返回其节点值的前序遍历。

例如，给定一个 3叉树 :

![[Pasted image 20200922222113.png]]

返回其前序遍历: [1,3,5,6,2,4]。

Solution

1. 递归

• 基于递归方法的先序遍历

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
	def VLR(self, root):
		if root:
			self.ans.append(root.val)
			for i in root.children:
				VLR(i)
    
	def preorder(self, root: 'Node') -> List[int]:
        self.ans = []
        self.VLR(root)
        return self.ans

2. 循环

• 用栈（准确地说是个list）保存待遍历节点；准确的说，保存的是出现覆盖，需要对值求和的pair
• 使用tuple代替常规的单个元素入栈
• n1, n2 = stack.pop()可以改为pop(0)，只是更改了处理的优先顺序
• 注意两个节点其中一个为空时的处理

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

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1 or not t2:
            return t1 or t2
        else:
            stack = [(t1, t2)]
            while stack:
                n1, n2 = stack.pop()
                n1.val += n2.val
                if n1.left:
                    if n2.left:
                        stack.append((n1.left, n2.left))
                else:
                    if n2.left:
                        n1.left = n2.left

                if n1.right:
                    if n2.right:
                        stack.append((n1.right, n2.right))
                else:
                    if n2.right:
                        n1.right = n2.right

            return t1