【递归】 145 二叉树的后序遍历

题目

给定一个二叉树返回他的后序遍历

思路

非递归用两个栈实现。第一个栈是前序的思路，放入根右左，（代码顺序是根左右），第二个栈实现逆序的功能

代码

递归：

public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); helper(root,res); return res; } public void helper(TreeNode root,List<Integer> res ){ if(root!=null){ if(root.left!=null){ helper(root.left,res); } if(root.right!=null){ helper(root.right,res); } res.add(root.val); } }

非递归：

public List<Integer> preorderTraversal1(TreeNode root){ List<Integer> res = new ArrayList<>(); Deque<TreeNode> stack1 = new LinkedList<>(); Deque<TreeNode> stack2 = new LinkedList<>(); stack1.push(root); if(root!=null){ while(!stack1.isEmpty()){ root = stack1.pop(); stack2.push(root); if(root.left!=null){ stack1.push(root.left); } if(root.right!=null){ stack1.push(root.right); } } while(!stack2.isEmpty()){ res.add(stack2.pop().val); } } return res; }