代码随想录-刷题第十四天

本文主要是介绍代码随想录-刷题第十四天，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

理论基础

二叉树的种类：满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树。

二叉树的存储方式：链式存储、线性存储。

二叉树的遍历方式：深度遍历（前序、中序、后序），广度遍历（层次遍历）。

深度遍历力扣对应的三道题目：

144. 二叉树的前序遍历

145. 二叉树的后序遍历

94. 二叉树的中序遍历

二叉树递归遍历

递归前序遍历代码

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new LinkedList<>();if (root == null) {return res;}// 前序遍历结果特点：第一个是根节点的值，接着是左子树，最后是右子树res.add(root.val);res.addAll(preorderTraversal(root.left));res.addAll(preorderTraversal(root.right));return res;}
}

递归后序遍历代码

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new LinkedList<>();if (root == null) {return res;}res.addAll(postorderTraversal(root.left));res.addAll(postorderTraversal(root.right));res.add(root.val);return res;}
}

递归中序遍历代码

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new LinkedList<>();if (root == null) {return res;}res.addAll(inorderTraversal(root.left));res.add(root.val);res.addAll(inorderTraversal(root.right));return res;}
}

二叉树的迭代遍历

前序迭代遍历

思路：先将根节点放入栈中，然后从栈中弹出节点放进数组，将弹出节点的右孩子放入栈中，将弹出节点的左孩子放入栈中。直到栈空。（注意：要先将右孩子入栈，再将左孩子入栈，这样出栈的顺序才是中、左、右，才符合前序遍历）。

class Solution {public List<Integer> preorderTraversal(TreeNode root) {// 迭代法，利用栈辅助操作Deque<TreeNode> stack = new ArrayDeque<>();List<Integer> ans = new ArrayList<>();if (root == null) return ans;stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();ans.add(node.val); // 中if (node.right != null) {stack.push(node.right); // 右}if (node.left != null) {stack.push(node.left); // 左}}// 从栈中取出来就是左 右 ，顺序是中 左 右 符合前序return ans;}
}

后序迭代遍历

思路：根据前序遍历来修改得到，调换左右孩子入栈的顺序，出栈顺序就是中、右、左，然后将数组反转，就得到左、右、中的遍历顺序，符合后序遍历。

class Solution {public List<Integer> postorderTraversal(TreeNode root) {// 迭代法，利用栈辅助操作。Deque<TreeNode> stack = new ArrayDeque<>();List<Integer> ans = new ArrayList<>();if (root == null) return ans;stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();ans.add(node.val); // 中if (node.left != null) {stack.push(node.left); // 左}if (node.right != null) {stack.push(node.right); // 右}}// 从栈中取出来顺序是 右 左 ，最后顺序为 中 右 左 // 反转数组后是 左 右 中，符合后序Collections.reverse(ans);return ans;}
}

中序迭代遍历

思路：迭代法中，中序遍历的处理顺序和访问顺序是不一致的，需要借助指针来帮助遍历访问节点，栈用来处理节点。先将指针指向根节点，只要指针或栈不为空，就进行遍历操作，如果指针不为空，当前元素入栈，指针指向左孩子，如果指针为空，指针指向栈中的出栈元素，将元素值存入数组中，然后指针指向当前元素的右孩子。

class Solution {public List<Integer> inorderTraversal(TreeNode root) {// 迭代法，用栈记录遍历过的元素Deque<TreeNode> stack = new ArrayDeque<>();List<Integer> ans = new ArrayList<>();TreeNode current = root;while (current != null || !stack.isEmpty()) {if (current != null) {stack.push(current);current = current.left;} else {current = stack.pop();ans.add(current.val);current = current.right;}}return ans;}
}

二叉树的统一遍历

思路：递归遍历无法统一写法的原因是无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。解决方法是将访问的节点放入栈中，把要处理的节点也放入栈中，但紧接着要放入一个空指针作为标记。（注意：Java中Stack可以push(null)而Deque不可以）

前序代码：

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();if (root != null) st.push(root);while (!st.empty()) {TreeNode node = st.peek();if (node != null) {// 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中st.pop(); // 添加右节点（空节点不入栈）if (node.right != null) st.push(node.right); // 添加左节点（空节点不入栈）if (node.left != null) st.push(node.left);// 添加中节点st.push(node);// 中节点访问过，但是还没有处理，加入空节点做为标记。st.push(null);} else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.peek();    // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;}
}

中序代码：

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();if (root != null) st.push(root);while (!st.empty()) {TreeNode node = st.peek();if (node != null) {// 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中st.pop(); // 添加右节点（空节点不入栈）if (node.right != null) st.push(node.right); // 添加中节点st.push(node);// 中节点访问过，但是还没有处理，加入空节点做为标记。st.push(null);// 添加左节点（空节点不入栈）if (node.left != null) st.push(node.left);    } else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.peek();    // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;}
}

后序代码：

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();if (root != null) st.push(root);while (!st.empty()) {TreeNode node = st.peek();if (node != null) {// 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中st.pop(); // 添加中节点st.push(node); // 中节点访问过，但是还没有处理，加入空节点做为标记。st.push(null); // 添加右节点（空节点不入栈）if (node.right != null) st.push(node.right);// 添加左节点（空节点不入栈）if (node.left != null) st.push(node.left);} else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.peek();    // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;}
}