个人中心
文章发布
退出
作者热门文章
- Java锁的逻辑（结合对象头和ObjectMonitor）
- 还在用饼状图？来瞧瞧这些炫酷的百分比可视化新图形（附代码实现）⛵
- 自动注册实体类到EntityFrameworkCore上下文，并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
26
4
二叉树主要有两种遍历方式:
深度优先遍历：先往深走，遇到叶子节点再往回走.
广度优先遍历：一层一层的去遍历.
。
。
。
对比图可以理解一下遍历的过程，前中后序遍历涉及递归和迭代两种方法讲解.
前序遍历： https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/ 。
中序遍历： https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/ 。
后序遍历： https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/ 。
层序遍历： https://leetcode.cn/problems/binary-tree-level-order-traversal/submissions/ 。
感兴趣的可以去 练练手 ！！！ 。
前序遍历的顺序是 中左右 ，即先根节点、左子树、右子树，那么我们先考虑递归进行求解.
要打印出前序遍历节点的数值，所以参数里需要 放节点的数值 ，除了这一点就不需要在处理什么数据了也不需要有返回值，所以递归函数返回类型就是 void .
Traversal(TreeNode root, List<Integer> list) 。
当前遍历的节点是空了，那么本层递归就要要结束了，所以如果当前遍历的这个节点是空，就直接 return .
if (cur == NULL) return ; 。
前序遍历是中左右的循序，所以在单层递归的逻辑，是要 先取中节点的数值 .
list.add(root.val),
Traversal(root.left, list),
Traversal(root.right, list); 。
所以总体的递归代码如下:
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>
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>
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
;
}
preorder(root.left, result);
result.add(root.val); //注意
preorder(root.right, result);
}
}
对于迭代法，难度 会更大一点！！！ 。
中序遍历是左中右，但是代码和上面有一些不同，中序遍历是左中右，先访问的是 二叉树顶部的节点 ，然后一层一层向下访问，直到到达树左面的 最底部 ， 再开始处理节点 （也就是在把节点的数值放进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>
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
;
}
preorder(root.left, result);
preorder(root.right, result);
result.add(root.val);
//
注意
}
}
对于迭代法，会前序遍历难度 会小一点！！！ 。
先序遍历是中左右，后续遍历是左右中，那么我们只需要 调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转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<List<Integer>> resList =
new
ArrayList<List<Integer>>
();
public
List<List<Integer>>
levelOrder(TreeNode root) {
checkFun02(root);
return
resList;
}
public
void
checkFun02(TreeNode node) {
if
(node ==
null
)
return
;
Queue
<TreeNode> que =
new
LinkedList<TreeNode>
();
que.offer(node);
while
(!
que.isEmpty()) {
List
<Integer> itemList =
new
ArrayList<Integer>
();
int
len =
que.size();
while
(len > 0
) {
TreeNode tmpNode
=
que.poll();
itemList.add(tmpNode.val);
if
(tmpNode.left !=
null
) que.offer(tmpNode.left);
if
(tmpNode.right !=
null
) que.offer(tmpNode.right);
len
--
;
}
resList.add(itemList);
}
}
}
主要就是建立一个 队列 ，依次对出队列的数的 左右子树入队 ，同时记录下 当前队列的大小 ，这样可以每一次得到 一层的数 .
怎么样，看完以后是不是简单多了，当然得有一点点这个方面 基础 ，不然看起来还是有点费劲！！！ 。
。
最后此篇关于二叉树的遍历的文章就讲到这里了,如果你想了解更多关于二叉树的遍历的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
26
4
0
我是一名优秀的程序员,十分优秀！