精华内容
下载资源
问答
  • 前序遍历 (preorder traversal) - 中序遍历 (inorder traversal) - 后序遍历 (postorder traversal) 1. 前序遍历 (preorder traversal) - 中序遍历 (inorder traversal) - 后序遍历 (postorder traversal) 遍历的...

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

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

    • 遍历的递归实现。
    • 遍历的非递归实现 - 使用栈的非递归实现。
    1. 二叉树的深度优先遍历的非递归做法是采用栈,广度优先遍历的非递归做法是采用队列。
    2. 深度优先对每一个可能的分支路径深入到不能再深入为止,先序遍历、中序遍历、后序遍历属于深度优先遍历。
    3. 广度优先遍历也称为层次遍历,从上往下,从左往右访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。
    typedef struct TREENODE
    {
    	struct TREENODE *left;
    	struct TREENODE *right;
    	struct TREENODE *parent;
    	int data;
    } TreeNode;
    

    2. Example

    在这里插入图片描述

    2.1 前序遍历 (preorder traversal)

    首先访问根结点,然后前序遍历其左子树,最后前序遍历其右子树。
    遍历结果:A B D H I E J C F G

    2.2 中序遍历 (inorder traversal)

    首先中序遍历根结点的左子树,然后访问根结点,最后中序遍历其右子树。
    遍历结果:H D I B J E A F C G

    2.3 后序遍历 (postorder traversal)

    首先后序遍历根结点的左子树,然后后序遍历根结点的右子树,最后访问根结点。
    遍历结果:H I D J E B F G C A

    3. Example

    在这里插入图片描述

    3.1 中序遍历 (inorder traversal)

    首先中序遍历根结点的左子树,然后访问根结点,最后中序遍历其右子树。
    遍历结果:B D C A E H G K F

    我们从根节点 A 看起,遍历 A 的左子树。
    A 的左子树存在,找到 B,此时 B 看做根节点,遍历 B 的左子树。
    B 的左子树不存在,返回 B,根据 [左根右] 的遍历规则,记录 B,遍历 B 的右子树。
    B 的右子树存在,找到 C,此时 C 看做根节点,遍历 C 的左子树。
    C 的左子树存在,找到 D。由于 D 是叶子节点,无左子树,记录 D。D 无右子树,返回 C,根据 [左根右] 的遍历规则,记录 C,遍历 C 的右子树。
    C 的右子树不存在,返回 B,B 的右子树遍历完,返回 A。A 的左子树遍历完毕,根据 [左根右] 的遍历规则,记录 A,遍历 A 的右子树。

    A 的右子树存在,找到 E,此时 E 看做根节点,遍历 E 的左子树。
    E 的左子树不存在,返回 E,根据 [左根右] 的遍历规则,记录 E,遍历 E 的右子树。
    E 的右子树存在,找到 F,此时 F 看做根节点,遍历 F 的左子树。
    F 的左子树存在,找到 G,此时 G 看做根节点,遍历 G 的左子树。
    G 的左子树存在,找到 H,由于 H 是叶子节点,无左子树,记录 H。H 无右子树,返回 G,根据 [左根右] 的遍历规则,记录 G,遍历 G 的右子树。
    G 的右子树存在,找到 K,由于 K 是叶子节点,无左子树,记录 K。K 无右子树,返回 G,根据 [左根右] 的遍历规则,记录 F,遍历 F的右子树。
    F 的右子树不存在,返回 F,E 的右子树遍历完毕,返回 A。A 的右子树也遍历完毕。
    遍历结果:B D C A E H G K F

    4. Example

    在这里插入图片描述

    4.1 前序遍历 (preorder traversal)

    首先访问根结点,然后前序遍历其左子树,最后前序遍历其右子树。
    遍历结果:A B D E G H C F

    4.2 中序遍历 (inorder traversal)

    首先中序遍历根结点的左子树,然后访问根结点,最后中序遍历其右子树。
    遍历结果:D B G E H A C F

    4.3 后序遍历 (postorder traversal)

    首先后序遍历根结点的左子树,然后后序遍历根结点的右子树,最后访问根结点。
    遍历结果:D G H E B F C A

    4.4 层序遍历 (breadth-first traversal)

    遍历结果:A B C D E F G H

    前序、中序、后序是针对根节点而言的,左右子树的遍历顺序不变。前序就是根节点最先遍历,然后左右子树。中序就是根节点放在中间遍历。后序就是把根节点放在最后遍历。

    5. 前序遍历 (preorder traversal)

    二叉树的深度优先遍历的非递归做法是采用栈 (stack)。
    首先访问根结点,然后前序遍历其左子树,最后前序遍历其右子树。

    5.1 Example

    1. 设置一个栈,将根节点 push 到栈中。
    2. 循环检测栈是否为空,若不空,则取出栈顶元素,保存其值。
    3. 查看栈顶元素右子节点是否存在,若存在则 push 到栈中。查看栈顶元素左子节点,若存在,则 push 到栈中。
    4. 继续回到 2. 执行,直到栈空。

    在这里插入图片描述

    5.2 Example

    在这里插入图片描述

    1. 设置一个栈,将根节点 push 到栈中 (push(root))。
    2. node = pop(), list.add(node.val)
    3. push(node.right)
    4. push(node.left)
    5. 循环步骤 3. 直到栈空。

    在这里插入图片描述

    6. 中序遍历 (inorder traversal)

    二叉树的深度优先遍历的非递归做法是采用栈 (stack)。
    首先中序遍历根结点的左子树,然后访问根结点,最后中序遍历其右子树。

    在这里插入图片描述

    1. 设置一个栈。
    2. 将根节点 root,以及 root 的持续左孩子都压入栈中。
    3. node = pop(), list.add(node.val)
    4. root = node.right
    5. 循环步骤 2. 直到栈为空且 rootNULL

    在这里插入图片描述

    7. 后序遍历 (postorder traversal)

    二叉树的深度优先遍历的非递归做法是采用栈 (stack)。
    首先后序遍历根结点的左子树,然后后序遍历根结点的右子树,最后访问根结点。

    在这里插入图片描述

    1. 设置一个栈,将根节点 push 到栈中 (push(root))。
    2. node = pop()
    3. list.add(0 , node.val)
    4. push(node.left)
    5. push(node.right)
    6. 循环步骤 2. 直到栈空。

    在这里插入图片描述

    展开全文
  • 1. 原本可以正常运行的项目,突然出现这个错: ... In order to reduce its length classpath file can be used. Would you like to enable classpath file mode for all run configurations of your project?En...

    前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到教程。

    1. 原本可以正常运行的项目,突然出现这个错:

    Command line is too long. In order to reduce its length classpath file can be used.
    Would you like to enable classpath file mode for all run configurations of your project?Enable

    2. 解决方法:

    修改项目下 .idea\workspace.xml,找到标签 <component name="PropertiesComponent"> , 在标签里加一行  <property name="dynamic.classpath" value="true" />

     

    展开全文
  • 94. Binary Tree Inorder Traversal

    千次阅读 2020-09-15 22:54:18
    94. Binary Tree Inorder Traversal 1. 问题 Given a binary tree, return the inorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recursive ...

    94. Binary Tree Inorder Traversal

    1. 问题

    Given a binary tree, return the inorder traversal of its nodes’ values.

    Example:

    Input: [1,null,2,3]
       1
        \
         2
        /
       3
    
    Output: [1,3,2]
    

    Follow up: Recursive solution is trivial, could you do it iteratively?

    2. 官方题解

    2.1 方法一:递归

    定义 inorder(root) 表示当前遍历到root 节点的答案,那么按照定义,我们只要递归调用 inorder(root.left) 来遍历 root 节点的左子树,然后将 root 节点的值加入答案,再递归调用inorder(root.right) 来遍历 root 节点的右子树即可,递归终止的条件为碰到空节点

    /**
     * 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().
     */
    
    void inorder(struct TreeNode* root, int* res, int* resSize) {
        if (!root) {
            return;
        }
        inorder(root->left, res, resSize);
        res[(*resSize)++] = root->val;
        inorder(root->right, res, resSize);
    }
    
    int* inorderTraversal(struct TreeNode* root, int* returnSize) {
        int* res = malloc(sizeof(int) * 501);
        *returnSize = 0;
        inorder(root, res, returnSize);
        return res;
    }
    

    复杂度分析:

    • 时间复杂度O(n),其中 n为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
    • 空间复杂度O(n)。空间复杂度取决于递归的栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n)的级别。

    2.2 方法二:使用栈

    方法一的递归函数我们也可以用迭代的方式实现,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而我们在迭代的时候需要显式地将这个栈模拟出来,其他都相同,具体实现可以看下面的代码。
    在这里插入图片描述

    int* inorderTraversal(struct TreeNode* root, int* returnSize) {
        *returnSize = 0;
        int* res = malloc(sizeof(int) * 501);
        struct TreeNode** stk = malloc(sizeof(struct TreeNode*) * 501);
        int top = 0;
        while (root != NULL || top > 0) {
            while (root != NULL) {
                stk[top++] = root;
                root = root->left;
            }
            root = stk[--top];
            res[(*returnSize)++] = root->val;
            root = root->right;
        }
        return res;
    }
    
    

    复杂度分析:

    • 时间复杂度O(n),其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
    • 空间复杂度O(n)。空间复杂度取决于递归的栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n)的级别。

    2.3 方法三:Morris算法中序遍历

    Morris 遍历算法是另一种遍历二叉树的方法,它能将非递归的中序遍历空间复杂度降为 O(1)

    Morris 遍历算法整体步骤如下(假设当前遍历到的节点为 xx):

    • 如果 xx 无左孩子,先将 xx 的值加入答案数组,再访问 xx 的右孩子,即 x=x.right
    • 如果 xx 有左孩子,则找到 xx 左子树上最右的节点(即左子树中序遍历的最后一个节点,xx 在中序遍历中的前驱节点),我们记为 predecessor。根据predecessor 的右孩子是否为空,进行如下操作:
      • predecessor 的右孩子为空,则将其右孩子指向 xx,然后访问 xx 的左孩子,即 x=x.left
      • 如果predecessor 的右孩子不为空,则此时其右孩子指向 xx,说明我们已经遍历完 xx 的左子树,我们将predecessor 的右孩子置空,将 xx 的值加入答案数组,然后访问 xx 的右孩子,即 x =x.right
    • 重复上述操作,直至访问完整棵树。

    在这里插入图片描述

    int* inorderTraversal(struct TreeNode* root, int* returnSize) {
        int* res = malloc(sizeof(int) * 501);
        *returnSize = 0;
        struct TreeNode* predecessor = NULL;
    
        while (root != NULL) {
            if (root->left != NULL) {
                // predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
                predecessor = root->left;
                while (predecessor->right != NULL && predecessor->right != root) {
                    predecessor = predecessor->right;
                }
    
                // 让 predecessor 的右指针指向 root,继续遍历左子树
                if (predecessor->right == NULL) {
                    predecessor->right = root;
                    root = root->left;
                }
                // 说明左子树已经访问完了,我们需要断开链接
                else {
                    res[(*returnSize)++] = root->val;
                    predecessor->right = NULL;
                    root = root->right;
                }
            }
            // 如果没有左孩子,则直接访问右孩子
            else {
                res[(*returnSize)++] = root->val;
                root = root->right;
            }
        }
        return res;
    }
    

    复杂度分析:

    • 时间复杂度O(n),其中 n为二叉搜索树的节点个数。Morris 遍历中每个节点会被访问两次,因此总时间复杂度为 O(2n)=O(n)
    • 空间复杂度O(1)无需开辟栈空间,这是最大的优点
    展开全文
  • Column ‘XXXX’ in order clause is ambiguous问题解决 今天sql查询报错: Column ‘create_time’ in order clause is ambiguous 原因是我多表查询,这个列两个表都有,需要指定一下哪个表的。 ...

    Column ‘XXXX’ in order clause is ambiguous问题解决

    今天sql查询报错:

    Column ‘create_time’ in order clause is ambiguous

    原因是我多表查询,这个列两个表都有,需要指定一下哪个表的。

    展开全文
  • No mapping found for [limit_time] in order to sort on 大概意思是按limit_time排序时找不到该字段的映射类型 如下图所示,查询21个分片,15个成功,6个失败,这样肯定达不到排序目的 二、解决方案 既然找不...
  • 94. Binary Tree Inorder Traversal(https://leetcode-cn.com/problems/binary-tree-inorder-traversal/) 用栈的方法来做: def inorderTraversal ( root ) : res = [ ] node_stack = [ ] p = ...
  • Column 'XXXX' in order clause is ambiguous

    千次阅读 2019-06-26 17:41:46
    问题原因: 列名指定的模棱两可。多表关联查询的时候不同的表中存在相同名称的列,在SQL中没有写清是哪张表的字段。 问题解决: 检查列名前是否指定了具体的表名称 ...
  • Set fielddata=true on [actorList.name] in order to load fielddata in memory by uninverting the inverted index. Note that this can however use significant memory. Alternatively use a keyword field ...
  • sql查询报错: 原因:多表查询的时候,多个表中都有create_time的字段 解决办法:将这个字段取个别名即可
  • 可能是console打印了 …test
  • In order to specify a config file use redis-server.exe /path/to/redis.conf 意思是没有使用默认的conf文件 解决办法:在命令行中执行 redis-server.exe redis.windows.conf,就可以了。 ...
  • 今天sql查询报错: Column 'create_time' in order clause is ambiguous原因是我多表查询,这个列两个表都有,需要指定一下哪个表的。
  • def iterative_inorder(self, root, res):#迭代中序遍历 stack = [] while root or stack: if root: stack.append(root) root = root.left else: root = stack.pop() res.append(root.val) root = root....
  • Binary Tree Inorder Traversal (二叉树的中序遍历) 题目描述: Given a binary tree, return the inorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 ...
  • 安装Redis编译测试的时候报如下错误: 查阅大神们的博客后记录如下解决方法: wget ...tar xzvf tcl8.6.1-src.tar.gz -C /usr/local/ cd /usr/local/tcl8.6.1/unix/ ./configure ma...
  • 拿preorder+inorder为例。 1. preorder的第一个数必然是根节点 2. 在inorder数组中查找这个数,得到rootIndex 3. rootIndex左边的数组即为left child node,右边的数组right node 4. 左右数组分别递归。 // ...
  • 在这里勾选,太隐蔽了,很多时候看不到,折腾了好久
  • In order to be iterable, non-array objects must have a [Symbol.iterator]() method.找了很久都没发现哪里错了,总说我试图破坏不可迭代实例的结构无效。为了具有可迭代性,非数组对象必须有一个[Symbol....
  • [10992] 24 Apr 14:12:37.689 # Warning: no config file specified, using the default ... In order to specify a config file use redis-server.exe /path/to/redis.conf [10992] 24 Apr 14:12:37.699 # Crea...
  • 1,可能是因为使用展开运算符或使用可迭代对象的时候,因为当前对象不是可迭代对象或者展开运算未在数组或者对象中展开,将循环的数组...uni-swipe-action-item v-for="(item,index) in details" :key="item.sourceNo
  • Intellij IDEA运行报Command line is too long解法 ... In order to reduce its length classpath file can be used. Would you like to enable classpath file mode for all run configurations o...
  • 在编译Redis的时候成功之后,提示“Hint: It's a good idea to run 'make test' ;)”,我们可以运行测试,确认Redis的功能是否正常。 [root@jeespring redis-5.0.7]# make && make test ...
  • Caused by: org.elasticsearch.index.query.QueryShardException: No mapping found for [avg_pv] in order to sort on 查看对应的index后这个index没有数据 创建的时候是有默认的_default_ mapping的 我用...
  • Binary Tree Inorder Traversal

    千次阅读 2014-06-05 20:58:21
    void inorder(TreeNode *root) { if (root == NULL) return; inorder(root->left); result.push_back(root->val); inorder(root->right); } vector<int> inorderTraversal(TreeNode *root) { result.clear...
  • 普通sql语句: SELECT REC_ID,ORDER_UPDATE_RULE,ACTIVITY_ID FROM PLT_ACTIVITY_...WHERE ((ORDER_GEN_RULE = 1 OR ORDER_GEN_RULE = 2 ) AND TENANT_ID = 'uni076' AND ACTIVITY_ID = '112202' AND ACTIVITY_ST...
  • redies启动显示Warning: no config file specified, using the default config. In order to specify a config file use ‘redis-server /path/to/redis.conf’ 这是因为更改了配置文件redis.conf, ...
  • 笔者在阿里云Centons7下安装Redis并且配置服务时,遇到如下错误:You need tcl 8.5 or newer in order to run the Redis testmake: *** [test] Error 1解决方案:1、下载 ...
  • 下载一个demo运行提示处理方法:as - setting 在搜索里面输入SDK 把8.0 的下载即可运行

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,044,356
精华内容 417,742
关键字:

inorder