赞
踩
给定一个二叉树,返回它的 前序 遍历。
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
题目地址:https://leetcode-cn.com/problems/binary-tree-preorder-traversal/description/
两种方式:
方法一(利用栈实现):
public class Solution { public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new LinkedList<>(); if(root == null) return res; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()){ TreeNode cur = stack.pop(); res.add(cur.val); if(cur.right != null) stack.push(cur.right); if(cur.left != null) stack.push(cur.left); } return res; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
方法二(采用递归方式):
public class Solution { // Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new LinkedList<>(); if(root == null) return null; System.out.println(root.val); res.add(root.val); preorderTraversal(root.left); preorderTraversal(root.right); return res; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。