【LintCode 题解】腾讯算法面试题：二叉树的前序遍历
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【LintCode 题解】腾讯算法面试题：二叉树的前序遍历，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2148字，纯文字阅读大概需要4分钟。
内容图文
题目描述
给出一棵二叉树，返回其节点值的前序遍历。
-
首个数据为根节点，后面接着是其左儿子和右儿子节点值，"#"表示不存在该子节点。
- 节点数量不超过20
样例 1:
输入：{1,2,3}
输出：[1,2,3]
解释：
1
/ \
2 3
它将被序列化为{1,2,3}
前序遍历
样例 2:
输入：{1,#,2,3}
输出：[1,2,3]
解释：
1
\
2
/
3
它将被序列化为{1,#,2,3}
前序遍历
题解
非递归方式实现前序遍历时，首先存入当前节点值，然后先将右儿子压入栈中，再将左儿子压入栈中。对栈中元素遍历访问。
国内大厂面试除了操作系统和计算机网络这些基础外，还需要熟练掌握算法和数据结构。自己刷题来准备的话至少需要3个月的时间，当然通过算法课程，一般能节省大把时间，快的话一个月时间就能应对大厂算法面试。
Version 0: Non-Recursion (Recommend)
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> preorder = new ArrayList<Integer>();
if (root == null) {
return preorder;
}
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
preorder.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return preorder;
}
}
//Version 1: Traverse
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
traverse(root, result);
return result;
}
// 把root为跟的preorder加入result里面
private void traverse(TreeNode root, ArrayList<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
traverse(root.left, result);
traverse(root.right, result);
}
}
//Version 2: Divide & Conquer
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
// null or leaf
if (root == null) {
return result;
}
// Divide
ArrayList<Integer> left = preorderTraversal(root.left);
ArrayList<Integer> right = preorderTraversal(root.right);
// Conquer
result.add(root.val);
result.addAll(left);
result.addAll(right);
return result;
}
}
九章算法 企业博客 发布了472 篇原创文章 · 获赞 1678 · 访问量 38万+ 私信 关注
内容总结
以上是互联网集市为您收集整理的【LintCode 题解】腾讯算法面试题：二叉树的前序遍历全部内容，希望文章能够帮你解决【LintCode 题解】腾讯算法面试题：二叉树的前序遍历所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。