前言：最近一个学习小组里大家约定每天刷算法题（虽然近期因为题目难度变难变为了两天一道），没想到的是几个组员居然不约而同地说出了代码随想录这个名字，正是“英雄所见略同”，最近已经是刷了有一阵子了，期间虽然偶然有做笔记，又因为这样那样的事情写得断断续续很零碎，实在凑不出一篇博客来，最近写到了二叉树，有了些感悟和时间，正好整理出篇博客来记录。
代码随想录：https://www.programmercarl.com/
二叉树
二叉树的递归遍历
递归：在函数的定义中使用函数自身的方法
因为二叉树的左右子树还是二叉树，所以可以使用递归的方法。前中后序遍历时使用递归则可以写出非常简洁优美的代码，并且在前中后切换时也仅仅只需要改变几行代码之间的顺序，代码的结构是保持不变的。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorder(root, result);
return result;
}
public void preorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
}
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}
void inorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
inorder(root.left, list);
list.add(root.val);
inorder(root.right, list);
}
}
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postorder(root, res);
return res;
}
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> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null){
stack.push(node.right);
}
if (node.left != null){
stack.push(node.left);
}
}
return result;
}
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()){
if (cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
}
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.left != null){
stack.push(node.left);
}
if (node.right != null){
stack.push(node.right);
}
}
Collections.reverse(result);
return result;
}
}
|
二叉树的统一迭代法
上文的二叉树迭代遍历可以看到，前后序遍历是可以转化的，而中序遍历则与前后序遍历的很不同，而我们也巧妙地找到了左右序遍历和中序遍历时的循环，前后序遍历的转化和中序遍历循环的寻找都是让人鼓掌叫好的巧思。那么事情就只能到此为止了吗，毕竟目前的解法看起来实现算不上优雅，中序遍历和前后序遍历完全不同，而前后序遍历严格上来说也因为最后的翻转操作并不完全统一。那么能否实现格式相同的前后中序迭代遍历呢？首先我们要知道为什么上文的迭代法和递归不同，因为上文的迭代法中的中序遍历，由于我们需要将当前的根节点先存放在栈中，而我们又无法区分栈中哪些是已经做过根节点的节点，而我们的解决方法是先确定左节点，等左节点剔出后，栈中露出来的自然就是它的根节点，我们事实上变相地“标记”了哪些是曾经的根节点，那么我们可以尝试其他的标记方法，这里采用的方式一种是直接在曾经的根节点后面放上一个空节点作为标记，一种则更加简单粗暴，直接给每个节点增加一个字段用于标记。
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;
}
}
class Command {
TreeNode node;
int type;
Command(TreeNode node, int type){
this.node = node;
this.type = type;
}
}
class Solution {
public static List<Integer> preorderTraversal(TreeNode root) {
Stack<Command> stack = new Stack<>();
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
stack.push(new Command(root, 0));
while(!stack.isEmpty()) {
Command command = stack.pop();
if (command.type == 0) {
if (command.node.right != null) stack.push(new Command(command.node.right, 0));
if (command.node.left != null) stack.push(new Command(command.node.left, 0));
stack.push(new Command(command.node, 1));
} else {
res.add(command.node.val);
System.out.println(command.node.val);
}
}
return res;
}
}
|
