原题
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3] 1
\
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
解法
思想
递归、迭代，类似 leetcode94-二叉树的中序遍历
代码
递归：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> ans = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root!=null){
ans.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
}
return ans;
}
}
迭代：
public class Solution {
public List <Integer> inorderTraversal(TreeNode root) {
List <Integer> res = new ArrayList<>();
Stack <TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
res.add(curr.val);
curr = curr.left;
}
curr = stack.pop();
curr = curr.right;
}
return res;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode144-%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e5%89%8d%e5%ba%8f%e9%81%8d%e5%8e%86/
相关推荐
-
leetcode82-删除排序链表中的重复元素II
原题 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。 示例 1: 输入: 1->2->3->3->4->4->5 输出: 1->2->5 示...
-
leetcode836-矩形重叠
原题 矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。 如果相交的面积为正，则称两矩形重叠。需要...
-
leetcode695-岛屿的最大面积
原题 给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围...
-
leetcode103-二叉树的锯齿形层次遍历
原题 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 例如:给定二叉树: [3,9,20,null,nul...
-
leetcode66-加一
原题 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以...
-
蓝桥杯试题-大小写转换
原题 资源限制 时间限制：1.0s 内存限制：256.0MB 问题描述 输入一个字符串，将大写字符变成小写、小写变成大写，然后输出 输入格式 acbAB 输出格式 ACBab ...
-
leetcode572-另一个树的子树
原题 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树...
-
leetcode56-合并区间
原题 给出一个区间的集合，请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]]...
-
蓝桥杯试题-哈夫曼树
原题 Description Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1}，用这列...
-
leetcode450-删除二叉搜索树中的节点
原题 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。 一...
