力扣:94. 二叉树的中序遍历

力扣:94. 二叉树的中序遍历,第1张

题目链接:94. 二叉树的中序遍历
题目:

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

示例 1:

输入:root = [1,null,2,3]
输出:[1,3,2]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

提示:

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

思路和算法:
本题使用递归法会比较容易些,明确递归三要素就可以很快的解决,具体三要素的讲解见:叫你写递归——递归三部曲。
在本题中,三要素是指:
(1)确定递归函数的参数和返回值:因为要打印出后序遍历节点的数值,所以参数里需要传入vector在放节点的数值,除了这一点就不需要在处理什么数据也不需要什么返回值,所以递归函数返回类型可以敲定为void;
即:void traversal(TreeNode* cur, vector& res) {}
(2)确定终止条件:在递归的过程中,什么才能算递归结束了呢,当然是当前遍历的节点是空,那么本层递归就要结束了,所以,如果当前遍历的这个节点是空,直接return;
即:if (!cur) return;
(3)确定单层递归的逻辑:后序遍历是左中右的顺序,所以在单层递归的逻辑,是先递归左子二叉树,然后再取中节点的数值放入结果数组,最后再递归右子二叉树;即:

traversal(cur->left, res);  //左
res.push_back(cur->val);    //中
traversal(cur->right, res); //右

代码(c++):

/**
 * 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<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(root, res);
        return res;
    }
private:
    void traversal(TreeNode* cur, vector<int>& res) {
        if (!cur) return;   //当前节点为空为终止条件
        traversal(cur->left, res);  //左
        res.push_back(cur->val);    //中
        traversal(cur->right, res); //右
    }
};

关于进阶里的问题,采用迭代法。
代码(c++):
在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。

/**
 * 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<int> inorderTraversal(TreeNode* root) {
        vector<int> res;    //结果数组
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        //如果栈内有数据或者当前节点不为空(指针用来辅助遍历)
        while (cur || !stk.empty()) {
            if (cur) {  //指针指向叶子节点
                stk.push(cur);
                cur = cur->left;    //指针遍历左子二叉树 //左
            }
            else {  //指针遍历到叶子节点
                cur = stk.top();
                res.push_back(cur->val);  //将栈顶元素放入结果数组    //中
                stk.pop();  //d出栈顶元素
                cur = cur->right;   //右
            }
        }
        return res;
    }
};

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1295810.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-10
下一篇 2022-06-10

发表评论

登录后才能评论

评论列表(0条)

保存