首页 / 算法 / LeetCode OJ：Binary Tree Inorder Traversal（中序遍历二叉树）

LeetCode OJ：Binary Tree Inorder Traversal（中序遍历二叉树）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode OJ：Binary Tree Inorder Traversal（中序遍历二叉树），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1471字，纯文字阅读大概需要3分钟。

内容图文

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?
中序遍历二叉树，递归遍历当然很容易，题目还要求不用递归，下面给出两种方法：

递归：

             1
            /*
            *

             2
             * Definition for a binary tree node.

             3
             * struct TreeNode {

             4
             *     int val;

             5
             *     TreeNode *left;

             6
             *     TreeNode *right;

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

             8
             * };

             9
            */
            10
            class
             Solution {

            11
            public
            :

            12     vector<int> inorderTraversal(TreeNode* root) {
13if(!root) return ret;
14        tranverse(root);
15return ret;
16    }
1718void tranverse(TreeNode * root)
19    {
20if(!root) return;
21         tranverse(root->left);
22         ret.push_back(root->val);
23         tranverse(root->right);
24    }
25private:
26     vector<int> ret;
27 };

迭代：

             1
            class
             Solution {

             2
            public
            :

             3     vector<int> inorderTraversal(TreeNode* root) {
 4         vector<int> ret;
 5if(!root) return ret;
 6         map<TreeNode *, bool> m;
 7         stack<TreeNode *> s;
 8        s.push(root);
 9while(!s.empty()){
10             TreeNode * t = s.top();
11if(t->left && !m[t->left]){
12                 m[t->left] = true;
13                 s.push(t->left);
14                 t = t->left;
15continue;
16            }
17             ret.push_back(t->val);
18            s.pop();
19if(t->right && !m[t->right]){
20                 m[t->right] = true;
21                 s.push(t->right);
22                 t = t->right;
23            }
24        }
25return ret;
26    }
27 };

 

原文：http://www.cnblogs.com/-wang-cheng/p/4912136.html

内容总结

以上是互联网集市为您收集整理的LeetCode OJ：Binary Tree Inorder Traversal（中序遍历二叉树）全部内容，希望文章能够帮你解决LeetCode OJ：Binary Tree Inorder Traversal（中序遍历二叉树）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1204439.html

来源：【匿名】