二叉树的遍历,递归和非递归 向右看齐 2024-04-17 05:44 23阅读 0赞 1,中序遍历 非递归版本,借助一个辅助 vector<int> ans; vector<int> inorderTraversal(TreeNode* root) { TreeNode *node = root; stack<TreeNode *> mstack; while(node != NULL || !mstack.empty()) { while(node != NULL) { mstack.push(node); // 注意这里入栈不能写指针,写结点 node = node->left; } ans.push_back(mstack.top()->val); // 注意这里是 . node = mstack.top()->right; mstack.pop(); } return ans; } 递归版本,简洁 vector<int> ans; vector<int> inorderTraversal(TreeNode* root) { if(root != NULL) { inorderTraversal(root->left); ans.push_back(root->val); inorderTraversal(root->right); } return ans; } 2,二叉树的后续遍历 非递归版本,后续遍历稍微麻烦点,通过设置一个 “前一个节点”变量,来记录下一次应该访问的结点 vector<int> ans; vector<int> postorderTraversal(TreeNode* root) { if(root == NULL) return ans; stack<TreeNode*> mstack; TreeNode* pre = NULL; //前一个节点 while(!mstack.empty()|| root != NULL) { if(root != NULL) { mstack.push(root); root = root->left; } else { root=mstack.top(); if(root->right == NULL || root->right == pre) { //如果右子树不存在,则接下来该访问根节点。 mstack.pop(); ans.push_back(root->val); pre = root; root = NULL; } else { //否则柚子树存在,就先访问右子树 pre = NULL; root = root->right; } } } return ans; } 递归版本,简洁 vector<int> ans; vector<int> postorderTraversal(TreeNode* root) { if(root != NULL) { postorderTraversal(root->left); postorderTraversal(root->right); ans.push_back(root->val); } return ans; }
还没有评论,来说两句吧...