NC161 题解 | #二叉树的中序遍历#

题意分析

• 给你一棵二叉树，需要你给出这棵二叉树的中序遍历的序列。

思路分析

• 这是一个很经典的题目，主要的考察点就是DFS递归的思想，首先，我们需要知道什么是中序遍历？中序遍历就是先遍历二叉树的左子树，然后遍历二叉树的根节点，然后遍历二叉树的右子树。对于左右子树，同样执行这样的操作即可。最后得到的就是中序遍历的序列。

• 我们可以看到，具体的命名是根据根节点的被遍历的顺序决定的，这个方便记忆.

写法一 C++

• 代码如下
  • 所有的节点都需要被遍历一遍，时间复杂度为O(n)
  • 每次递归都需要开辟栈空间，递归的次数为树的高度，所以空间复杂度为O(logn)

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    // 中序遍历,左子树->根节点->右子树
    void dfs(vector<int> &ans,TreeNode* root){
        // 先遍历左子树
        if(root->left){
            dfs(ans,root->left);
        }
        // 然后遍历当前根节点
        if(root==NULL){
            return;
        }else{
            ans.push_back(root->val);
        }
        // 然后遍历右子树
        if(root->right){
            dfs(ans,root->right);
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        vector<int> ans;
        if(root==NULL){
            return ans;
        }
        dfs(ans,root);
        return ans;
    }
};

写法二 GO

• 代码如下
  • 所有的节点都需要被遍历一遍，时间复杂度为O(n)
  • 每次递归都需要开辟栈空间，递归的次数为树的高度，所以空间复杂度为O(logn)

package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
*/
func dfs(ans *[]int,root *TreeNode){
    // 如果当前的结点指针为空
    if(root==nil){
        return
    }
    // 递归左子树
    dfs(ans,root.Left)
    *ans=append(*ans,root.Val)
    // 递归右子树
    dfs(ans,root.Right)
}
func inorderTraversal( root *TreeNode ) []int {
    // write code here
    var ans []int
    if(root==nil){
        return ans;
    }
    dfs(&ans,root)
    return ans;
}