【算法第十一天7.25】二叉树前、中、后递归、非递归遍历

递归

思路

1、确定返回值和方法参数：需要集合来存放树各节点的值，最后打印出来，所以需要一个list集合作为参数，不断迭代；除此之外不需要有返回值

2、确定终止条件：当前节点为空时，则需要结束本次方法调用（结束本次递归），用return

3、确定单次递归逻辑：中序遍历，左中右 处理，对root的处理就是加入到集合中

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}public void inorder(TreeNode root, List<Integer> list){// 当前传入的root为null结束本方法的执行，继续下面方法的执行if(root == null) return;inorder(root.left,list);list.add(root.val);inorder(root.right,list);}
}

非递归

思路

1、终止条件：栈为空 且 cur节点为空

2、如果左孩子一直不为空，则需要一直入栈

3、左孩子为空后，则开始pop节点（入集合），pop出的节点也要看其左孩子，所以cur要指向pop出的节点，继续判断其左孩子

class Solution {public List<Integer> inorderTraversal(TreeNode root){Stack<TreeNode> stack = new Stack<>();List<Integer> res = new ArrayList<>();if(root == null) return res;TreeNode cur = root;// 这里除了判空，也有可能栈空了，但是右节点还没有处理（未入栈）while(!stack.isEmpty() || cur != null){// 如果左孩子一直存在，则要一路把左孩子都存进去，直到cur为空if(cur != null){stack.push(cur);cur = cur.left;// cur为空时，则说明左边已经循环到低了，可以开始pop并入集合// 也需要开始处理右节点，右节点处理也是要一路把左节点先存进去，重复上述步骤// 所以要将右节点命为cur，也就是要处理的节点}else{cur = stack.pop();res.add(cur.val);cur = cur.right;}}return res;}
}

递归

思路

1、确定返回值和方法参数：需要集合来存放树各节点的值，最后打印出来，所以需要一个list集合作为参数，不断迭代；除此之外不需要有返回值

2、确定终止条件：当前节点为空时，则需要结束本次方法调用（结束本次递归），用return

3、确定单次递归逻辑：前序遍历，中左右 处理，对root的处理就是加入到集合中，对左右节点处理，就是不断递归

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

非递归

思路

1、先让root入栈，接着pop出来，定义为node，先把node.val添加到集合中，再去判断其是否有左右孩子，一定先右后左，出栈顺序相反

2、循环终止条件：栈为空则说明所有节点已经处理完毕

class Solution {public List<Integer> preorderTraversal(TreeNode root){Stack<TreeNode> stack = new Stack<>();List<Integer> res = new ArrayList<>();if(root == null) return res;stack.push(root);// 这里除了判空，不需要其它条件，即使出栈空了，后面还会有节点push进去while(!stack.isEmpty()){TreeNode node = stack.pop();res.add(node.val);if(node.right != null) stack.push(node.right);if(node.left != null) stack.push(node.left);}return res;}
}

递归

思路

1、确定返回值和方法参数：需要集合来存放树各节点的值，最后打印出来，所以需要一个list集合作为参数，不断迭代；除此之外不需要有返回值

2、确定终止条件：当前节点为空时，则需要结束本次方法调用（结束本次递归），用return

3、确定单次递归逻辑：后序遍历，左右中 处理，对**root（传入节点）**的处理就是加入到集合中，对左右节点处理，就是不断递归

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

非递归

思路

入栈顺序中、左、右；出栈顺序：中、右、左；翻转顺序：左、右、中

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) return res;Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop();res.add(node.val);if (node.left != null){stack.push(node.left);}if (node.right != null){stack.push(node.right);}}// 入栈顺序中、左、右；出栈顺序：中、右、左；翻转顺序：左、右、中Collections.reverse(res);return res;}
}