⼆叉树的前序遍历
1.问题描述
给定⼀个⼆叉树，返回它的前序遍历。
⽰例:
输⼊: [1,null,2,3]
1
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
2.求解
递归
代码如下
/*
* 执⾏⽤时：0 ms, 在所有 Java 提交中击败了100.00% 的⽤户
* 内存消耗：36.2 MB, 在所有 Java 提交中击败了99.57% 的⽤户
* */
public List<Integer> preorderTraversal(TreeNode root) {
二叉树前序中序后序图解
List<Integer> ans = new ArrayList<>();
access(root,ans);
return ans;
}
private void access(TreeNode root,List ans){
if(root == null){
return;
}
ans.add(root.val);
access(root.left,ans);
access(root.right,ans);
}
时间复杂度：O(n)，遍历每个节点⼀次
空间复杂度：O(n)，每次递归栈的开销，递归平均空间复杂度为O(logn)，最坏情况下树为链状，n个节
点每个节点都要使⽤⼀个栈，此时空间复杂度为O(n) ps：⼆叉树的前序、中序、后序遍历是相对于遍历根节点的顺序命名的
前序遍历：先中后左右
中序遍历：先左后中再右
后序遍历：先左右后中
使⽤递归⽅法差距不⼤
中序遍历
private void access(TreeNode root,List ans){
if(root == null){
return;
}
access(root.left,ans);
ans.add(root.val);
access(root.right,ans);
}
后序遍历
private void access(TreeNode root,List ans){
if(root == null){
return;
}
access(root.left,ans);
access(root.right,ans);
ans.add(root.val);
}
迭代
当使⽤递归的时候编译器为我们维护了⼀个栈，但是这个栈对于我们隐式的、是不可见的
那我们可以使⽤迭代显式的维护⼀个栈，来模拟递归的过程
对于个⽗节点和左右⼦节点，我们⾸先将⽗节点压⼊栈中，然后弹出⽗节点，再将右⼦节点压⼊栈中，最后将左⼦节点压⼊栈中
如没有新元素再⼊栈，那么此时弹出顺序则式⽗、左节点、右节点
代码如下
/*
* 执⾏⽤时：0 ms, 在所有 Java 提交中击败了100.00% 的⽤户
* 内存消耗：36.2 MB, 在所有 Java 提交中击败了99.78% 的⽤户
* */
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if(root == null){
return ans;
}
Deque<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
ans.add(node.val);
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
return ans;
}
ps：迭代的中序、后续遍历如何处理可以看这篇[] Morris

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。