https://www.nowcoder.com/practice/0bf071c135e64ee2a027783b80bf781d?tpId=295&tqId=1512964&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295
中序遍历，遍历顺序：左节点->当前节点->右节点
GO
切片slice模拟栈
package main
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型一维数组
*/
func inorderTraversal( root *TreeNode ) []int {
// write code here
stack := make([]*TreeNode,0)
rc := root
result := make([]int,0)
for rc != nil || len(stack) > 0{
for rc != nil{
stack = append(stack,rc)
rc = rc.Left
}
rc = stack[len(stack)-1]
stack = stack[:len(stack)-1]
result = append(result, rc.Val)
rc = rc.Right
}
return result
}
运行时间 9ms
占用内存 1212KB
C++
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型vector
*/
vector<int> inorderTraversal(TreeNode* root) {
// write code here
vector<int> result;
stack<TreeNode*> st;
TreeNode* rc = root;
while(rc != nullptr || st.size() > 0){
while(rc != nullptr){
st.push(rc);
rc = rc->left;
}
rc = st.top();
st.pop();
result.push_back(rc->val);
rc = rc->right;
}
return result;
}
};
运行时间 4ms
占用内存 524KB
原文链接: https://www.cnblogs.com/starter-songudi/p/17076836.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/314788
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
