借这个题目延展一下,一次写完前序,后序,中序的递归和非递归写法
一. 递归解法
如下所示,只要调整dfs遍历顺序就可以轻松得到先序,中序,后序的遍历结果了;
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res= new LinkedList<>();
dfs(res,root);
return res;
}
private void dfs(List<Integer> res, TreeNode root) {
if (root==null){
return;
}
dfs(res,root.left);
res.add(root.val);
dfs(res,root.right);
}
}
二.非递归解法
1.先序
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res= new LinkedList<>();
Stack<TreeNode> stack=new Stack<>();
if (root==null){
return res;
}
//打印,左,右
stack.push(root);
while (!stack.isEmpty()){
TreeNode curr = stack.pop();
res.add(curr.val);
//栈先进后出,我们要后面打印右树,因此先把右树放进去
if (curr.right!=null){
stack.push(curr.right);
}
if (curr.left!=null){
stack.push(curr.left);
}
}
return res;
}
中序
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res= new LinkedList<>();
Stack<TreeNode> stack=new Stack<>();
while (root!=null||stack.size()>0){
//直到不能继续向左再停止
if (root!=null){
stack.add(root);
root=root.left;
//如果root为null说明stack最新的一个结点无左节点,
// 因此直接先打印本节点,再迭代调用B结点
}else {
TreeNode pop = stack.pop();
res.add(pop.val);
root=pop.right;
}
}
return res;
}
后序
前面俩我都是用的栈方式,后序遍历我也提供一个栈方式;
后续遍历跟先序遍历比较像,这里是定义了两个栈,把打印的放在打印栈stack2里
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res= new LinkedList<>();
if (root==null){
return res;
}
//先序栈
Stack<TreeNode> stack1=new Stack<>();
//打印栈
Stack<Integer> stack2=new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()){
TreeNode pop = stack1.pop();
stack2.push(pop.val);
if (pop.left!=null){
stack1.push(pop.left);
}
if (pop.right!=null){
stack1.push(pop.right);
}
}
//打印
while (!stack2.isEmpty()){
res.add(stack2.pop());
}
return res;
}
跟leetcode学到,这里再提供一个高效的,双向链表版本
{
LinkedList<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
while (root != null) {
res.addFirst(root.val);
stack.push(root);
root = root.right;
}
if (!stack.isEmpty()) {
root = stack.pop();
root = root.left;
}
}
return res;
}
网友评论