【刷 题】：二叉树的中序遍历

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

示例1：输入：root = [1,null,2,3] 输出：[1,3,2]

示例2：输入：root = []  输出：[]

示例3：输入：root = [1] 输出：[1]

来源：力扣

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector inorderTraversal(TreeNode* root) {vectornums;                    //设置存放结点的值的数组stacksta;                //设置存放遍历结点的指针的栈while(root!= nullptr || !sta.empty())   //指向二叉树的指针不为空或者栈不为空则循环{while(root != nullptr)             //指针不为空遍历左子树{sta.push(root);                //将指向左子树上结点的指针存入到栈内root = root->left;             //指针继续指向左节点}root = sta.top();                  //指针指向栈中顶部存放指针的指向的地方sta.pop();                         //弹出栈内的指针nums.push_back(root->val);         //将指针指向的结点上的值存储到数组中root = root->right;                //指针指向右节点}return nums;                           //返回数组}
};

解题思路：将指向左子树的指针存储到栈中，当遍历到空时，开始存储栈顶的指向的结点的值，当遇到存在右节点时，依旧循环遍历，直到栈内为空和节点为空，即遍历完成

class Solution {
public:void inorder(TreeNode* root, vector& res) {if (!root) {return;}inorder(root->left, res);res.push_back(root->val);inorder(root->right, res);}vector inorderTraversal(TreeNode* root) {vector res;inorder(root, res);return res;}
};

官方答案，递归的方法

class Solution {
public:vector inorderTraversal(TreeNode* root) {vector res;TreeNode *predecessor = nullptr;while (root != nullptr) {if (root->left != nullptr) {// predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止predecessor = root->left;while (predecessor->right != nullptr && predecessor->right != root) {predecessor = predecessor->right;}// 让 predecessor 的右指针指向 root，继续遍历左子树if (predecessor->right == nullptr) {predecessor->right = root;root = root->left;}// 说明左子树已经访问完了，我们需要断开链接else {res.push_back(root->val);predecessor->right = nullptr;root = root->right;}}// 如果没有左孩子，则直接访问右孩子else {res.push_back(root->val);root = root->right;}}return res;}
};

详细解题思路说明，请点击官方解释

力扣https://leetcode.cn/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！