【leetcode】第六章 二叉树part01

递归遍历

144. 二叉树的前序遍历

// 前序遍历
public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();preOrder(root, res);return res;}private void preOrder(TreeNode root, List<Integer> res) {if (root == null) return;res.add(root.val);preOrder(root.left, res);preOrder(root.right, res);}

94. 二叉树的中序遍历

public List<Integer> inorderTraversal(TreeNode root) {// 递归List<Integer> res = new ArrayList<>();inOrder(root, res);return res;}private void inOrder(TreeNode root, List<Integer> res) {if (root == null) return;inOrder(root.left, res);res.add(root.val);inOrder(root.right, res);}

145. 二叉树的后序遍历

public List<Integer> postorderTraversal(TreeNode root) {// 递归List<Integer> res = new ArrayList<>();postOrder(root, res);return res;}private void postOrder(TreeNode root, List<Integer> res) {if (root == null) return;postOrder(root.left, res);postOrder(root.right, res);res.add(root.val);}

非递归遍历

• 前序

public List<Integer> preorderTraversal(TreeNode root) {// 非递归List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();while (root != null || !stack.isEmpty()) {// 一直将左节点压入栈中while (root != null) {res.add(root.val); // 根节点首先访问stack.push(root);root = root.left;}root = stack.pop();root = root.right; }return res;}

• 中序

public List<Integer> inorderTraversal(TreeNode root) {// 非递归List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();while (root != null || !stack.isEmpty()) {while (root != null) {stack.push(root);root = root.left;}root = stack.pop();res.add(root.val);root = root.right;}return res;}

• 后序

public List<Integer> postorderTraversal(TreeNode root) {// 非递归List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode prev = null;while (root != null || !stack.isEmpty()) {// 将左节点压入栈while (root != null) {stack.push(root);root = root.left;}root = stack.pop();// 后序遍历的过程中在遍历完左子树跟右子树cur都会回到根结点。// 所以当前不管是从左子树还是右子树回到根结点都不应该再 操作了，应该退回上层。// 如果是从右边再返回根结点，应该回到上层。// 主要就是判断出来的是不是右子树，是的话就可以把根节点=加入到list了if (root.right == null || root.right == prev) {res.add(root.val);prev = root;root = null;}else {stack.push(root);root = root.right;}}return res;}