BM25 二叉树的后序遍历

标签：遍历 TreeNode BM25 nullptr int 二叉树 rc stack result

https://www.nowcoder.com/practice/1291064f4d5d4bdeaefbf0dd47d78541?tpId=295&tqId=2291301&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

package main
import . "nc_tools" /* * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型一维数组 */ func postorderTraversal( root *TreeNode ) []int { // write code here rc := root stack := make([]*TreeNode,0,100) result := make([]int,0,100) var prev *TreeNode for rc != nil || len(stack) > 0{ if rc == nil{ rc = stack[len(stack)-1] if rc.Right != nil && rc.Right != prev{ rc = rc.Right   }else{ result = append(result,rc.Val) prev = rc stack = stack[:len(stack)-1] rc = nil } } for rc != nil{ stack = append(stack,rc) rc = rc.Left } } return result }

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> postorderTraversal(TreeNode* root) { // write code here TreeNode* rc = root; stack<TreeNode*> st; vector<int> result; TreeNode* prev = nullptr; while(rc != nullptr || st.size() > 0){ if(rc == nullptr){ rc = st.top(); if(rc->right != nullptr && rc->right != prev){ rc = rc->right; }else{ result.push_back(rc->val); prev = rc; st.pop(); rc = nullptr; } } while(rc != nullptr){ st.push(rc); rc = rc->left; }
} return result; } };

标签：遍历,TreeNode,BM25,nullptr,int,二叉树,rc,stack,result
From： https://www.cnblogs.com/starter-songudi/p/17077357.html