144.前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]

输出：[1,2,3]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [1]

输出：[1]

示例 4：

输入：root = [1,2]

输出：[1,2]

示例 5：

输入：root = [1,null,2]

输出：[1,2]

1.递归方法。用一个栈来存储遍历到的节点。前序遍历的顺序是根---左---右。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();//创建存储前序遍历的结果if(root == null){//树为null，直接返回return list;}Deque<Integer> stack = new LinkedList<>();//用一个栈来存储当前遍历到的节点preorder(root,list,stack);return list;}//根左右的顺序public void preorder(TreeNode node,List<Integer> list,Deque<Integer> stack){stack.push(node.val);//先将当前根节点加入栈list.add(stack.peek());//将当前根节点的值加入liststack.pop();//取出遍历过的节点if(node.left != null){//如果存在左子树，继续遍历左子树preorder(node.left,list,stack);}if(node.right != null){//如果存在右子树，继续遍历右子树preorder(node.right,list,stack);}}
}

   答案的递归写法：不需要辅助空间栈。

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

2.迭代。

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();//创建存储前序遍历的结果Deque<TreeNode> stack = new LinkedList<>();//用一个栈来存储当前遍历到的节点TreeNode node = root;while(node != null || !stack.isEmpty()){while(node != null){//先遍历左子树，一直到左子树不存在stack.push(node);//先将没个左子树的根节点加入队列list.add(node.val);node = node.left;}node = stack.pop();//取出当前的根节点node = node.right;//再去找右子树}return list;}
}

题源：力扣

145.后序遍历

1.递归：

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();postorder(root,list);return list;}//左、右、根public void postorder(TreeNode node,List<Integer> list){if(node == null){return;}if(node.left != null){postorder(node.left,list);}if(node.right != null){postorder(node.right,list);}list.add(node.val);}
}

2.迭代。

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();Deque<TreeNode> stack = new LinkedList<>();TreeNode node = root;//当前节点TreeNode pre = null;//前一个节点while(node != null || !stack.isEmpty()){while(node != null){//存在左子树，先把左子树的全部根节点加入栈stack.push(node);node = node.left;}node = stack.peek();//取出左子树的最后一个根节点//如果此时该节点没有右子节点即为叶子节点，则加入list；//或者当前节点的右子节点是上一个遍历过的节点，则该根节点的右子树已经遍历完毕，也将当前根节点加入listif(node.right == null || node.right == pre){list.add(node.val);stack.pop();pre = node;node = null;}else{//存在右子树，且右子树未被遍历过node = node.right;}}return list;}
}

题源：力扣