开发者社区> nomasp> 正文

LeetCode 94 Binary Tree Inorder Traversal(二叉树的中序遍历)+(二叉树、迭代)

简介: 版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50930671 翻译 给定一个二叉树,返回其中序遍历的节点的值。
+关注继续查看
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50930671

翻译

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

例如:
给定二叉树为 {1#, 2, 3}
   1
    \
     2
    /
   3
返回 [1, 3, 2]

备注:用递归是微不足道的,你可以用迭代来完成它吗?

原文

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

分析

虽然人家题目都说了递归是微不足道的,但咱还是先用递归写一遍吧。

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
    vector<int> v;

    vector<int> inorderTraversal(TreeNode* root) {
        if (root != NULL) {
            inorderTraversal(root->left);
            v.push_back(root->val);
            inorderTraversal(root->right);
        }
        return v;
    }
};

接下是是时候写成迭代咯~

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> tempStack;
        while (!tempStack.empty() || root != NULL) {
            if (root != NULL) {
                tempStack.push(root);
                root = root->left;
            }
            else {
                root = tempStack.top();
                result.push_back((tempStack.top())->val);
                tempStack.pop();
                root = root->right;
            }
        }
        return result;
    }
};

另有两道类似的题目:

LeetCode 144 Binary Tree Preorder Traversal(二叉树的前序遍历)+(二叉树、迭代)

LeetCode 145 Binary Tree Postorder Traversal(二叉树的后续遍历)+(二叉树、迭代)

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
LeetCode-94. 二叉树的中序遍历(day19)
LeetCode-94. 二叉树的中序遍历(day19)
7 0
树遍历专题:利用二叉树的中序遍历有序特性|Java 刷题打卡
树遍历专题:利用二叉树的中序遍历有序特性|Java 刷题打卡
8 0
leetcode算法94.二叉树的中序遍历
当给定一个二叉树的根节点 root ,如何返回它的中序遍历?本文带大家解决这个问题。
6 0
【每日一题】leetcode hard难度:二叉树最大路径和
【每日一题】leetcode hard难度:二叉树最大路径和
24 0
LeetCode 144 Binary Tree Preorder Traversal(二叉树的前序遍历)+(二叉树、迭代)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50931535 翻译 给定一个二叉树,返回其前序遍历的节点的值。
740 0
数据结构(二):二叉搜索树(Binary Search Tree)
二分法猜数字的游戏应该每个人都知道,通过对猜测数字“大了”、“小了”的情况判断,来猜出最终的数字。序列范围为 的集合,复杂度为 ,即最多需要 次可以猜到最终数字。
961 0
+关注
542
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载