leetcode 144(二叉树的前序遍历)
程序员文章站
2022-03-03 11:13:05
...
水题一道,题目如下
给定一个二叉树,返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
题解
1. 递归
import java.util.ArrayList;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> ansList = new ArrayList<>();
if (root != null) {
ansList.add(root.val);
ansList.addAll(preorderTraversal(root.left));
ansList.addAll(preorderTraversal(root.right));
}
return ansList;
}
}
3.迭代做法
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
stack = []
ans = []
stack.append(root)
if (root==None):
return []
while (stack != []):
node = stack.pop()
ans.append(node.val)
if (node.right!=None):
stack.append(node.right)
if (node.left!=None):
stack.append(node.left)
return ans
上一篇: 深搜-迷宫