Leecode热题100---94：二叉树的中序遍历

本文主要是介绍Leecode热题100---94：二叉树的中序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：
给定一个二叉树的根节点 root ，返回它的中序遍历。

递归思路：
中序遍历：中序遍历左子树，然后访问根，再中序遍历右子树；
切记：左子树为空或已遍历才可以访问根，然后中序遍历右子树！！！

递归算法实现：
若二叉树为空，则空操作，否则：
1、中序左子树—>2、访问根—>3、中序遍历右子树

C++：

#include<iostream>
#include<vector>
using namespace std;struct TreeNode
{int val;TreeNode*left;TreeNode*right;TreeNode();TreeNode(int x){val = x;left = right = nullptr;}TreeNode(int x,TreeNode *left,TreeNode *right){val = x;left = left;right = right;}
};class Solution
{
public:// 定义根节点的指针类型cur，vector用来存储中序遍历的序列// 中序遍历的递归算法，递归有返回值void traversal(TreeNode* cur,vector<int> &vec){if(cur ==nullptr) return;traversal(cur->left, vec);	// 左  递归调用// 存储根节点的值，此操作在中间为中序,若在前，则为前序遍历，在后为后序遍历vec.push_back(cur->val);	traversal(cur->right,vec);	// 右  递归调用}vector<int> inorderTraversal(TreeNode* root){vector<int> res;traversal(root,res);	// 定义vector,记录答案return res;}
};

python：
思路同上：

class TreeNode:def __init__(self,x):self.val = xself.left = Noneself.right = Noneclass Solution:def inorderTravelsal(self,root):res = []def dfs(cur):if cur ==None: return# # 前序遍历# res.append(cur.val)# dfs(cur.left)# dfs(cur.right)# 中序遍历dfs(cur.left)res.append(cur.val)dfs(cur.right)# # 后序遍历# dfs(cur.left)# dfs(cur.right)# res.append(cur.val)dfs(root)return res