Kiml's Blog
代码随想录算法训练营第十二天-二叉树理论基础、递归遍历、迭代遍历、统一迭代
Kiml Lv5
  2024-06-01 11:17:20   2024-06-25 15:51:44    1.9k 字  8 分钟  

  • 前言
    递归、迭代、统一迭代。都是看完解析之后完成的。统一迭代有点难理解。

  • 更新

1
24-06-03 初始记录

144 二叉树的前序遍历

题目链接：(https://leetcode.cn/problems/binary-tree-preorder-traversal/description/)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<Integer> preorderTraversal(TreeNode root) {  
    ArrayList<Integer> list = new ArrayList<>();  
    preOrder(root, list);  
    return list;  
}
/**  
 * 前序遍历
 * @param root 节点  
 * @param list 遍历结果  
 */  
private void preOrder(TreeNode root, ArrayList<Integer> list) {  
    if (root == null) {  
        return;  
    }  
    // 当前  
    list.add(root.val);  
    // 左子树  
    preOrder(root.left, list);  
    // 右子树  
    preOrder(root.right, list);  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**  
 * 迭代法  
 * 前序遍历 中左右  
 * @param root 根节点  
 * @return 结果  
 */  
public List<Integer> preorderTraversal(TreeNode root) {  
    ArrayList<Integer> list = new ArrayList<>();  
    if (root == null) {  
        return list;  
    }  
    Stack<TreeNode> stack = new Stack<>();  
    stack.push(root);  
    while (!stack.isEmpty()) {  
        TreeNode pop = stack.pop();  
        list.add(pop.val);  
  
        // 栈先进后出，先进右  
        if (pop.right != null) {  
            stack.push(pop.right);  
        }  
        if (pop.left != null) {  
            stack.push(pop.left);  
        }  
    }  
  
    return list;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public List<Integer> preorderTraversal(TreeNode root) {  
    ArrayList<Integer> list = new ArrayList<>();  
    Stack<TreeNode> stack = new Stack<>();  
    if (root != null) {  
        stack.push(root);  
    }  
    while (!stack.isEmpty()) {  
        TreeNode node = stack.peek();  
        if (node != null) {  
            stack.pop();  
            // 判断右节点  
            if (node.right != null) {  
                stack.push(node.right);  
            }  
            // 左节点  
            if (node.left != null) {  
                stack.push(node.left);  
            }  
            // 中间节点  
            stack.push(node);  
            stack.push(null);  
            // 只有到最后一个节点，才会进这个else  
        } else {  
            // 遇到空节点，说明后一个是要处理的节点，先弹出空节点  
            stack.pop();  
  
            // 再把要处理的节点弹出并加入到列表中  
            node = stack.peek();  
            stack.pop();  
            list.add(node.val);  
        }  
    }  
    return list;  
}

94 二叉树的中序遍历

题目链接：(https://leetcode.cn/problems/binary-tree-inorder-traversal/description/)

中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进 result 数组中），这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> inorderTraversal(TreeNode root) {  
    ArrayList<Integer> list = new ArrayList<>();  
    inOrder(root, list);  
    return list;  
}
/**  
 * 中序遍历  
 * @param root 节点  
 * @param list 遍历结果  
 */  
private void inOrder(TreeNode root, ArrayList<Integer> list) {  
    if (root == null) {  
        return;  
    }  
    inOrder(root.left, list);  
    list.add(root.val);  
    inOrder(root.right, list);  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**  
 * 迭代法  
 * 中序遍历 左中右  
 * @param root 根节点  
 * @return 结果  
 */  
public List<Integer> inorderTraversal(TreeNode root) {  
    ArrayList<Integer> list = new ArrayList<>();  
    if (root == null) {  
        return list;  
    }  
    Stack<TreeNode> stack = new Stack<>();  
    TreeNode cur = root;  
    while (!stack.isEmpty() || cur != null) {  
        if (cur != null) {  
            // 先遍历左子节点(直至到最后一个左子节点)  
            stack.push(cur);  
            cur = cur.left;  
        } else {  
            // 此时从栈里弹出的数据，就是要处理的数据  
            cur = stack.pop();  
            list.add(cur.val);  
            cur = cur.right;  
        }  
    }  
  
    return list;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**  
 * 中序遍历  
 * @param root 根节点  
 * @return 返回遍历结果  
 */  
public List<Integer> inorderTraversal(TreeNode root) {  
    ArrayList<Integer> list = new ArrayList<>();  
    Stack<TreeNode> stack = new Stack<>();  
    if (root != null) {  
        stack.push(root);  
    }  
    while (!stack.isEmpty()) {  
        TreeNode node = stack.peek();  
        if (node != null) {  
            stack.pop();  
            // 判断右节点  
            if (node.right != null) {  
                stack.push(node.right);  
            }  
            // 中间节点  
            stack.push(node);  
            stack.push(null);  
            // 左节点  
            if (node.left != null) {  
                stack.push(node.left);  
            }  
            // 只有到最后一个节点，才会进这个else  
        } else {  
            // 遇到空节点，说明后一个是要处理的节点，先弹出空节点  
            stack.pop();  
  
            // 再把要处理的节点弹出并加入到列表中  
            node = stack.peek();  
            stack.pop();  
            list.add(node.val);  
        }  
    }  
    return list;  
}

145 二叉树的后序遍历

题目链接：(https://leetcode.cn/problems/binary-tree-postorder-traversal/description/)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 递归法
public List<Integer> postorderTraversal(TreeNode root) {  
    ArrayList<Integer> list = new ArrayList<>();  
    postOrder(root, list);  
    return list;  
}  
  
/**  
 * 后序遍历  
 * @param root 节点  
 * @param list 遍历结果  
 */  
private void postOrder(TreeNode root, ArrayList<Integer> list) {  
    if (root == null) {  
        return;  
    }  
    postOrder(root.left, list);  
    postOrder(root.right, list);  
    list.add(root.val);  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**  
 * 后序遍历 左右中  
 * @param root 根节点  
 * @return 结果  
 */  
public List<Integer> postorderTraversal(TreeNode root) {  
    ArrayList<Integer> list = new ArrayList<>();  
    if (root == null) {  
        return list;  
    }  
    Stack<TreeNode> stack = new Stack<>();  
    stack.push(root);  
    while (!stack.isEmpty()) {  
        TreeNode pop = stack.pop();  
        list.add(pop.val);  
  
        // 栈先进后出，先进右  
        if (pop.left != null) {  
            stack.push(pop.left);  
        }  
        if (pop.right != null) {  
            stack.push(pop.right);  
        }  
    }  
    // 上部分代码与前序相同，left和right遍历顺序颠倒。得到的数组为中右左遍历得出的结果  
    // 翻转得到的结果，即为左右中遍历得出的结果  
    Collections.reverse(list);  
    return list;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public List<Integer> postorderTraversal(TreeNode root) {  
    ArrayList<Integer> list = new ArrayList<>();  
    Stack<TreeNode> stack = new Stack<>();  
    if (root != null) {  
        stack.push(root);  
    }  
    while (!stack.isEmpty()) {  
        TreeNode node = stack.peek();  
        if (node != null) {  
            stack.pop();  
            // 中间节点  
            stack.push(node);  
            stack.push(null);  
            // 判断右节点  
            if (node.right != null) {  
                stack.push(node.right);  
            }  
            // 左节点  
            if (node.left != null) {  
                stack.push(node.left);  
            }  
            // 只有到最后一个节点，才会进这个else  
        } else {  
            // 遇到空节点，说明后一个是要处理的节点，先弹出空节点  
            stack.pop();  
  
            // 再把要处理的节点弹出并加入到列表中  
            node = stack.peek();  
            stack.pop();  
            list.add(node.val);  
        }  
    }  
    return list;  
}

看解析

❗递归的三要素

文章讲解：(https://programmercarl.com/二叉树的递归遍历.html)

  1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

  2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

  3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

迭代法

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中所以所有递归的题目，理论上都可以使用栈解决。

题目链接/文章讲解/视频讲解：(https://programmercarl.com/二叉树的迭代遍历.html)

统一迭代

迭代法实现的先中后序，其实风格也不是那么统一，除了先序和后序，有关联，中序完全就是另一个风格了，一会用栈遍历，一会又用指针来遍历。
在迭代法的中序遍历中提到说使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

题目链接/文章讲解：(https://programmercarl.com/二叉树的统一迭代法.html)

代码随想录算法训练营第十二天-二叉树理论基础、递归遍历、迭代遍历、统一迭代
posts/a297f438/
作者
Kiml
发布于
2024-06-01 11:17
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 144 二叉树的前序遍历
  2. 94 二叉树的中序遍历
  3. 145 二叉树的后序遍历
  4. 看解析
    1. ❗递归的三要素
    2. 迭代法
    3. 统一迭代
© 2022 - 2025    Kiml
由 Hexo 驱动 & 主题 Keep
访客数 访问量
  1. 144 二叉树的前序遍历
  2. 94 二叉树的中序遍历
  3. 145 二叉树的后序遍历
  4. 看解析
    1. ❗递归的三要素
    2. 迭代法
    3. 统一迭代