题目链接 : https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
题目描述:
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]进阶: 递归算法很简单，你可以通过迭代算法完成吗？
思路:
两种方法实现, 递归 和 迭代
递归
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
def helper(root):
if not root:return
res.append(root.val)
helper(root.left)
helper(root.right)
helper(root)
return resjava
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res);
return res;
}
private void helper(TreeNode root, List<Integer> res) {
if (root == null) return;
res.add(root.val);
helper(root.left, res);
helper(root.right, res);
}
}迭代
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
p = root
stack = []
while p or stack:
while p:
res.append(p.val)
stack.append(p)
p = p.left
p = stack.pop().right
return resjava
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
TreeNode p = root;
List<Integer> res = new ArrayList<>();
while (p != null || !stack.isEmpty()) {
while (p != null) {
res.add(p.val);
stack.push(p);
p = p.left;
}
p = stack.pop().right;
}
return res;
}
}二叉树的前序,中序,后序,层序遍历的递归和迭代,一起打包送个你们!嘻嘻
思路:
递归:就是依次输出根,左,右,递归下去
迭代:使用栈来完成,我们先将根节点放入栈中,然后将其弹出,依次将该弹出的节点的右节点,和左节点,注意顺序,是右,左,为什么?因为栈是先入先出的,我们要先输出右节点,所以让它先进栈.
代码:
递归:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def helper(root):
if not root:
return
res.append(root.val)
helper(root.left)
helper(root.right)
helper(root)
return res迭代:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
if not root:
return res
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res思路:
递归:同理,顺序:左,右,根
迭代:这就很上面的先序一样,我们可以改变入栈的顺序,刚才先序是从右到左,我们这次从左到右,最后得到的结果取逆.
代码:
递归:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def helper(root):
if not root:
return
helper(root.left)
helper(root.right)
res.append(root.val)
helper(root)
return res迭代:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
if not root:
return res
stack = [root]
while stack:
node = stack.pop()
if node.left :
stack.append(node.left)
if node.right:
stack.append(node.right)
res.append(node.val)
return res[::-1]
思路:
递归:顺序,左右根
非递归:这次我们用一个指针模拟过程
代码:
递归:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
def helper(root):
if not root:
return
helper(root.left)
res.append(root.val)
helper(root.right)
helper(root)
return res
迭代:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
if not root:
return res
stack = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
思路:
非常典型的BFS
代码:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
res,cur_level = [],[root]
while cur_level:
temp = []
next_level = []
for i in cur_level:
temp.append(i.val)
if i.left:
next_level.append(i.left)
if i.right:
next_level.append(i.right)
res.append(temp)
cur_level = next_level
return res