首页 > 代码库 > leetcode:Binary Tree Inorder Traversal
leetcode:Binary Tree Inorder Traversal
一、 题目
给一个二叉树,中序遍历这个树,输出得到的值
二、 分析
这道题前面见到了,多次隔过去了,今天终于面对了,当时是没有好的思路,自习想想越是太难,Leetcode上的题,递归是统法啊!
方法一:递归
1. 开辟数组,递归左节点
2. 将中间结点放入数组
3. 递归有节点
方法二:使用数组和栈
1. 将根节点入栈
2. 设置标志或判断条件,一直向左入栈
3. 出栈并入数组
基本上递归和非递归思路就是这样,很简单的说。
/** * Definition for binary tree * 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> ans; inorder(root,ans); return ans; } void inorder(TreeNode *node,vector<int>&ans) { if(node == NULL) return; inorder(node->left,ans); ans.push_back(node->val); inorder(node->right,ans); } };
/** * Definition for binary tree * 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> ans; stack<TreeNode *> sta; TreeNode *ptr = root; while(!sta.empty()||ptr){ if(ptr){ sta.push(ptr); ptr = ptr->left; } else { ptr = sta.top(); sta.pop(); ans.push_back(ptr->val); ptr = ptr->right; } } return ans; } };
/** * Definition for binary tree * 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> ans; if(!root) return ans; stack<TreeNode *> sta; sta.push(root); while(!sta.empty()){ while(sta.top()->left) sta.push(sta.top()->left); TreeNode *t = sta.top(); ans.push_back(t->val); sta.pop(); if(!sta.empty()) sta.top()->left = NULL; if(t->right) sta.push(t->right); } return ans; } };
leetcode:Binary Tree Inorder Traversal
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。