首页天道酬勤steal some hours from the night,look forward to doing something

steal some hours from the night,look forward to doing something

admin 08-15 07:34 213次浏览
tree traversal (树的遍历) - 中序遍历 (inorder traversal) - 二叉树的中序遍历

树的遍历是当且仅当访问树中每个节点一次的过程。遍历可以解释为把所有的节点放在一条线上,或者将树线性化。

1. tree traversal (树的遍历) 1.1 深度优先搜索 (depth-first search,DFS)

我们采用深度作为优先级,从根节点开始一直到达某个确定的叶子节点,然后再返回根节点到达另一个分支。深度优先搜索策略可以根据根节点、左孩子树和右孩子树的相对顺序被细分为前序遍历、中序遍历和后序遍历。

前序遍历 (preorder traversal) - 中序遍历 (inorder traversal) - 后序遍历 (postorder traversal)

1.2 广度优先搜索 - 宽度优先搜索 - 横向优先搜索 (breadth-first search,BFS)

我们按照高度顺序一层一层的访问整棵树,高层次的节点将会比低层次的节点先被访问到。

下图中的节点依照不同的策略遍历,访问的顺序均为 1, 2, 3, 4, 5。宽度优先搜索划分层次为 [[1], [2, 3], [4, 5]]。

递归实现的效率一般比对应的非递归实现低。如果在函数中使用了两个递归调用,效率低下的问题就会变得更为严重。

2. 二叉树的中序遍历

给定一个二叉树,返回它的中序遍历。

输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2] int* inorderTraversal(struct TreeNode* root, int* returnSize)

输入参数 root 为 NULL 时,如果 return NULL,*returnSize 必须设置为 0。

2.1 迭代实现 - 数组模拟栈 (stack) 的操作 //============================================================================// Name : inorder traversal// Author : Yongqiang Cheng// Version : Feb 22, 2020// Copyright : Copyright (c) 2020 Yongqiang Cheng// Description : Hello World in C++, Ansi-style//============================================================================/* * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; *//** * Note: The returned array must be malloced, assume caller calls free(). */int* inorderTraversal(struct TreeNode* root, int* returnSize){int front = 0, idx = 0;struct TreeNode* STACK_DATA[512] ={ NULL };int *ret = (int *) malloc(512 * sizeof(int));struct TreeNode* pnode = NULL;*returnSize = 0;if (NULL == root){return NULL;}if (NULL == ret){return NULL;}front = -1;STACK_DATA[++front] = root;while (front >= 0){while (NULL != STACK_DATA[front]){pnode = STACK_DATA[front]->left;STACK_DATA[++front] = pnode;}--front;if (front >= 0){pnode = STACK_DATA[front];ret[idx] = pnode->val;idx++;STACK_DATA[front] = pnode->right;}}*returnSize = idx;return ret;}

3. 中序遍历 (inorder traversal)

中序遍历 (inorder traversal) 顺着左侧通路,自底而上依次访问沿途各节点及其右子树。

迭代式中序遍历 (出栈节点以深色示意)

4. 中序遍历 (inorder traversal) 4.1 递归方法

递归是经典的方法。

递归前序遍历:打印 - 左 - 右
递归中序遍历:左 - 打印 - 右
递归后序遍历:左 - 右 - 打印

递归实现复杂度分析
时间复杂度:O(n)。
空间复杂度:O(h),h 是树的高度。

递归实现是函数自己调用自己,一层层的嵌套下去,操作系统自动帮我们用栈来保存了每个调用的函数。递归的调用过程是不断往左边走,当左边走不下去了,就打印节点,并转向右边,然后右边继续这个过程。

4.2 迭代方法

基于栈的迭代方法。

迭代实现复杂度分析
时间复杂度:O(n)。
空间复杂度:O(h),h 是树的高度。

在树的深度优先遍历中 (前序、中序、后序遍历),递归方法直观,但考虑到效率,我们通常不推荐使用递归。栈迭代方法提高了效率,但对于不同的遍历顺序 (前序、中序、后序),循环结构差异很大。

References

https://leetcode-cn.com/

如何开发vue-dev-serverSpringCloudAlibaba使用Sentinel实现接口限流UCloud优刻得加入杨浦区数字化转型合作生态圈如何自己创建一个app(如何自己创建一个appstore的账号)linux如何清空某目录内文件-linux运维使用react创建上下文时找不到命名空间'ctx'错误-Typescript【Flink实时计算 UFlink】UFlink开发注意事项
中序遍历和后序遍历怎么确定一个树,已知一棵树的中序遍历和后序遍历 二叉树先序遍历和中序遍历,二叉树中序遍历过程
相关内容