Java教程

14 二叉树的中序遍历(Binary Tree Preorder Traversal)

本文主要是介绍14 二叉树的中序遍历(Binary Tree Preorder Traversal),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 1 题目
  • 2 描述
  • 3 解决方案
    • 3.1 递归算法
      • 3.1.1 遍历法(Traverse)
        • 思路
        • 源码
      • 3.1.2 分治法(Devide And Conquer)
        • 思路
        • 源码
    • 3.2 非递归算法
      • 3.2.1 二叉树遍历的非递归通用解法
        • 思路
        • 源码
        • 图解
    • 3.3 时间复杂度
    • 3.4 空间复杂度

1 题目

  二叉树的中序遍历(Binary Tree Preorder Traversal)

lintcode:题号——67,难度——easy

2 描述

  给出一棵二叉树,返回其节点值的中序遍历。

名词:

遍历

按照一定的顺序对树中所有节点进行访问的过程叫做树的遍历。

中序遍历

在二叉树中,首先遍历左子树,然后访问根结点,最后遍历右子树,在遍历左右子树时,仍然采用这种规则,这样的遍历方式叫做二叉树的中序遍历。

序列化规则:

使用大括号包裹节点序列来表示二叉树,首个数据为根节点,后面接着是其左儿子和右儿子节点值,"#"表示不存在该子节点,之后以此类推。

样例1:

输入:二叉树 = {1,2,3}
输出:[2,1,3]
解释:上述{1,2,3}序列按照序列化规则表示的二叉树如下

     1
    / \
   2   3

按照前序遍历规则,先根再左右子树,顺序即为[2,1,3]

样例2:

输入:二叉树 = {1,#,2,3}
输出:[1,3,2]
解释:上述{1,#,2,3}序列按照序列化规则表示的二叉树如下

        1
      /   \
    #       2
           /
          3

按照前序遍历规则,先根再左右子树,顺序同样为[1,3,2]

3 解决方案

  中序遍历与前序遍历[1]一样可以使用递归和非递归两类方式,递归和非递归各自的优缺点在前序遍历中也提到了。

3.1 递归算法

  递归写法比较简单,主要注意防止死循环,递归的过程中要明确递归的三要素。

递归的三要素:

  1. 递归的定义(递归函数的返回值、参数要如何定义)
  2. 递归的拆解(递归如何向下拆分)
  3. 递归的出口(递归的结束条件)

  递归又有两种形式,遍历和分治。

3.1.1 遍历法(Traverse)

思路

  遍历的整个过程可以看成是为了完成某项大任务,于是领导亲自下基层处理各项小任务,所有工作都“亲历亲为”,参与了所有工作最终完成了大任务。

遍历法的主要递归函数一般不带返回值,会拥有全局参数或者贯穿整个递归过程的函数参数用来处理数据。

源码

  C++版本:

/**
* @param root: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
vector<int> inorderTraversal(TreeNode * root) {
    // write your code here
    vector<int> result;
    traverse(root, result);

    return result;
}

// 遍历法的递归函数,没有返回值,函数参数result贯穿整个递归过程用来记录遍历的结果
void traverse(TreeNode * cur, vector<int> & result) // 递归三要素之定义
{
    if (cur == nullptr)
    {
        return; // 递归三要素之出口
    }

    // 此处与前序遍历不同,先处理左子树,再处理根节点,最后处理右子树
    traverse(cur->left, result); // 递归三要素之拆解
    result.push_back(cur->val);
    traverse(cur->right, result);
}

3.1.2 分治法(Devide And Conquer)

思路

  分治法的整个过程可以看成是为了完成某项大人物,于是领导把各项工作分派给各个下属,各个下属又把工作继续细分层层向下分派给基层人员,每一级都只需要获取下级完成的任务结果即可,最终所有层级任务都完成了,大任务也对应完成了。

分治法的主要递归函数一般需要有返回值,用来向上一层提供结果。

源码

  C++版本:

/**
* @param root: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
// 由于主函数的形式已经符合分治法需要的形式(具有合适的返回值),直接使用主函数做为递归函数
vector<int> inorderTraversal(TreeNode * root) {
    // write your code here
    vector<int> result;
    if (root == nullptr)
    {
        return result; // 递归三要素之出口
    }

    // 获取左子树的遍历结果
    vector<int> leftResult = inorderTraversal(root->left); // 递归三要素之拆解
    // 获取右子树的遍历结果
    vector<int> rightResult = inorderTraversal(root->right);

    // 此处与前序遍历不同,先处理左子树,再处理根节点,最后处理右子树
    result.insert(result.end(), leftResult.begin(), leftResult.end());
    result.push_back(root->val);
    result.insert(result.end(), rightResult.begin(), rightResult.end());

    return result;
}

3.2 非递归算法

3.2.1 二叉树遍历的非递归通用解法

思路

  在中序遍历的非递归算法中,与前序遍历[1:1]唯一的不同之处在于对节点的解析操作发生的时刻,前序遍历是“边入栈边解析”,而中序遍历是“出栈时解析”。

  1. 左穿入栈到底;
  2. 从栈内弹出当前节点,可能是左子树或者根节点(相对),出栈时解析;
  3. 右子树的根节点入栈,重复1、2步骤(即对右子树做中序遍历),直到满足循环结束条件,该二叉树的中序遍历即在结果序列中。

中序遍历的初始条件和循环结束条件在通用解法中与前序遍历一致。
初始条件:栈为空当前指针指向根节点
循环结束条件:栈为空当前指针为空

源码
/**
* @param root: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
vector<int> inorderTraversal(TreeNode * root) {
    // write your code here
    vector<int> result;
    if (root == nullptr)
    {
        return result;
    }

    stack<TreeNode *> nodeStack;
    TreeNode * cur = root;
    while (!nodeStack.empty() || cur != nullptr)
    {
        while (cur != nullptr)
        {
            nodeStack.push(cur);
            cur = cur->left;
        }

        cur = nodeStack.top();
        result.push_back(cur->val); // 此处是通用解法中唯一与前序遍历不同的地方,出栈时解析
        nodeStack.pop();
        cur = cur->right;
    }
}
图解

  在解法中,中序遍历的过程与前序遍历[1:2]基本一致,可以参考前序遍历的图解,区别只是解析操作发生的时刻不同。

3.3 时间复杂度

  对二叉树的遍历,不管使用什么方式都是将整棵树中的所有节点走一遍,所以算法的时间复杂度都为O(n)。

  关于二叉树和分治法的时间复杂度的更多内容,在前序遍历[1:3]中已经进行了计算分析。

3.4 空间复杂度

  算法的空间复杂度,分治法为O(n),上述其余方法都为O(1)。


  1. 二叉树的前序遍历:https://blog.csdn.net/SeeDoubleU/article/details/119834420 ↩︎ ↩︎ ↩︎ ↩︎

这篇关于14 二叉树的中序遍历(Binary Tree Preorder Traversal)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!