LeetCode 144. Binary Tree Preorder Traversal-二叉树的前序遍历(JAVA迭代及递归方法实现)
题目解读
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree [1,null,2,3]
,
1 \ 2 / 3
return [1,2,3]
.
Note: Recursive solution is trivial, could you do it iteratively?
题意:给一个二叉树,返回其前序遍历的结果。题目中提示,递归方法是微不足道的,可以使用迭代方法。
思路分析
前序遍历,访问顺序是 根节点->左孩子->右孩子。递归方法比较容易实现,具体思路见下面代码;迭代算法实现的主要思路如下:
- 首先判断是否为空树,是,则直接返回;不是,继续;
- 新建一个Stack栈存放未处理的树节点,将根节点压人栈;
- 当栈不为空时,循环执行以下操作:
将当前栈中存放的节点值添加到结果链表中;
判断当前节点是否存在右子树,有则入栈;
判断当前节点是否存在左子树,有则入栈;
(注:这里先push右孩子,再push左孩子,因为栈是先进后出的,左孩子后进,先出,才满足先序遍历的访问顺序 根-左-右。)
- 最后将结果链表返回。
如果一个树如下结果:
按上面的思路,访问二叉树及中间的存储状态如下,最终返回的结果链表顺序是:1、2、4、5、3、6。
代码实现
- 递归实现
/**
* 递归实现
* 根据先序遍历的特点,根->左->右
* @param root
* @return
*/
public List<Integer> preorderTraversalRecursive(TreeNode root) {
List<Integer> list = new ArrayList<>();
//判断是否为空树
if (root == null) {
return list;
}
list.add(root.val); //【根】
list.addAll(preorderTraversalRecursive(root.left)); //【左】通过addAll方法,将根节点的左子树,按preorderTraversalRecursive(root.left)返回的顺序,添加到列表尾部
list.addAll(preorderTraversalRecursive(root.right));//【右】通过addAll方法,将根节点的右子树,按preorderTraversalRecursive(root.right)返回的顺序,添加到列表尾部
return list;
}
- 迭代实现
/**
* 二叉树的前序遍历
* 非递归实现(迭代),借助堆栈实现
* 时间/空间复杂度O(n)
* @param root
* @return
*/
public List<Integer> preorderTraversalInteration(TreeNode root) {
List<Integer> result = new ArrayList<>(); //存放遍历之后的结果
Stack<TreeNode> stack = new Stack<>(); //存放未处理的节点
//判断是否为空树
if (root == null) {
return result;
}
stack.push(root); //将树根节点压入栈
while (! stack.isEmpty()){
TreeNode cur = stack.pop(); //指向当前节点
result.add(cur.val); //当前节点值添加到结果链表中
/**
* 判断当前节点是否存在右子树,有则入栈
* 判断当前节点是否存在左子树,有则入栈
* 这里先push右孩子,再push左孩子,因为栈是先进后出的,左后进,先出,才满足先序遍历
*/
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
return result;
}
恶补知识
(1)二叉树的前序遍历,访问顺序 根->左->右
(2)Stack类表示后进先出(LIFO)的对象堆栈,通过五个操作对类Vector进行了扩展,允许将向量是为堆栈。
·isEmpty():测试此向量是否不包含组件
·pop():移除堆栈顶部的对象,并最为此函数的值返回对象
·push(E item):把项压人堆栈顶部
(3)List中的方法
·add(E e):向列表的尾部添加指定的元素
·addAll(Collection<? extends E> c):添加制定collection中的所有元素到列表的结尾,顺序是指定collection的迭代器返回这些元素的顺序(可选操作)
(4)迭代与递归的区别
·迭代:循环结构,例如for,while循环,一般是x(n+1),x(n)之间的关系,x(n+1)=f(x(n))
·递归:递归是迭代的特例,自身调用自身的迭代。例如if else调用自己,并在合适时机退出。经典的斐波那契数列,Fn = Fn-1 + Fn-2。
分割线
小知识大道理,一点一滴积累。给点个赞吧
(个人微信公众号:TestOnTheRoad,搜索ID或者扫描下方二维码添加关注,关注测试开发工程师的成长之路)
上一篇: 企业网站怎么做好推广工作
下一篇: REST安全实践·3.DIGEST认证