144.二叉树的前序遍历

链接：144.二叉树的前序遍历
难度：Easy
标签：栈、树、深度优先搜索、二叉树
简介：给定一个二叉树，返回它的前序遍历。

题解 1 - typescript

• 编辑时间：2020-10-27
• 执行用时：84ms
• 内存消耗：40.2MB
• 编程语言：typescript
• 解法介绍：递归。

function preorderTraversal(root: TreeNode | null): number[] {
  const ans: number[] = [];
  preorder(root);
  return ans;
  function preorder(root: TreeNode | null) {
    if (root === null) return;
    ans.push(root.val);
    preorder(root.left);
    preorder(root.right);
  }
}

题解 2 - c

• 编辑时间：2021-11-27
• 内存消耗：5.7MB
• 编程语言：c
• 解法介绍：递归。

// 先计算当前节点，再递归左，再递归右
void preorder(struct TreeNode *root, int *arr, int *idx){
    if (!root) return ;
    arr[(*idx)++] = root->val;
    preorder(root->left, arr, idx);
    preorder(root->right, arr, idx);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int *arr = (int *)malloc(sizeof(int) * 100);
    *returnSize = 0;
    preorder(root, arr, returnSize);
    return arr;
}

题解 3 - java

• 编辑时间：2020-02-21
• 执行用时：1ms
• 内存消耗：38.2MB
• 编程语言：java
• 解法介绍：迭代。

class Solution {
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> list = new LinkedList<Integer>();
		if (root == null)
			return list;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode node = stack.pop();
			list.add(node.val);
			if(node.right!=null)stack.push(node.right);
			if(node.left!=null)stack.push(node.left);
		}
		return list;
	}
}

题解 4 - typescript

• 编辑时间：2020-10-27
• 执行用时：80ms
• 内存消耗：40.3MB
• 编程语言：typescript
• 解法介绍：迭代。

function preorderTraversal(root: TreeNode | null): number[] {
  const ans: number[] = [];
  if (root === null) return ans;
  const stack: TreeNode[] = [root];
  while (stack.length !== 0) {
    const node = stack.pop()!;
    ans.push(node.val);
    node.right && stack.push(node.right);
    node.left && stack.push(node.left);
  }
  return ans;
}

题解 5 - python

• 编辑时间：2024-02-11
• 执行用时：34ms
• 内存消耗：16.38MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

题解 6 - java

• 编辑时间：2020-02-21
• 内存消耗：37.8MB
• 编程语言：java
• 解法介绍：递归。

class Solution {
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> list = new LinkedList<Integer>();
		if (root == null)
			return list;
		preorder(root, list);
		return list;
	}
	public void preorder(TreeNode node, List<Integer> list) {
		list.add(node.val);
		if (node.left != null)
			preorder(node.left,list);
		if (node.right != null)
			preorder(node.right,list);
	}
}