BM24 二叉树的中序遍历

标签：TreeNode int BM24 中序 二叉树 rc root stack result

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

 

标签：TreeNode,int,BM24,中序,二叉树,rc,root,stack,result
From： https://www.cnblogs.com/starter-songudi/p/17076836.html