先序遍历、中序遍历二叉树非递归实现

柔情只为你懂 2022-07-16 03:21 288阅读 0赞

## 先序遍历 ##

[leetcode 144. binary-tree-preorder-traversal][]

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
            return preorderTraversalIteratively(root);
        }
        /* 先序遍历递归版本 */
        void preorderTraversalRecursion(TreeNode* root){
            if(root){
                cout<<root->val<<endl;
                preorderTraversalRecursion(root->left);
                preorderTraversalRecursion(root->right);
            }
        }
        /* 先序遍历非递归版本 */
        vector<int> preorderTraversalIteratively(TreeNode* root){
            stack<TreeNode*>S;  // 初始化栈 S
            vector<int>v;       // v 记录访问节点的顺序
            // 两种情况：
            // 只要左子树不为空那么就一直向左走
            // 走到最左边时，看是否有
            while(root || !S.empty()){
                // 左子树不为空一直往左走
                if(root){
                    v.push_back(root->val);  // 访问根节点
                    S.push(root); // 根节点入栈，因为左子树访问完毕时需要回来再访问右子树
                    root = root->left; // 访问左子树
                }
                // 走到最左边后，开始向右走
                else{
                    root = S.top();
                    S.pop();
                    root = root->right;
                }
            }
            return v;
        }
    };

## 中序遍历 ##

[leetcode 94. Binary Tree Inorder Traversal][]

/** * Definition for a binary tree node. * 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) {
            return inorderTraversalInteratively(root);
        }
        /* 中序遍历递归版本*/
        void inorderTraversalRecursion(TreeNode* root){
            if(root){
                inorderTraversalRecursion(root->left);
                cout<<root->val<<endl;  // 访问根节点
                inorderTraversalRecursion(root->right);
            }
        }
        /* 中序遍历非递归版本 */
        vector<int> inorderTraversalInteratively(TreeNode* root){
    
            stack<TreeNode*>S;
            vector<int>v;
    
            /* 第一种写法 while(root || !S.empty()){ if(root){ S.push(root); root = root->left; } else{ root = S.top(); v.push_back(root->val); // 注意与先序遍历的区别 S.pop(); root = root->right; } } */
    
            /* 第二种写法 */
            while(root || !S.empty()){
                /* 左子树全部入栈 */
                while(root){
                    S.push(root);
                    root = root->left;
                }
                if(!S.empty()){
                    root = S.top();
                    v.push_back(root->val);  // 访问根节点
                    S.pop();
                    root = root->right; // 下一次循环遍历右子树
                }
            }
    
            return v;
        }
    };

[leetcode 144. binary-tree-preorder-traversal]: https://leetcode.com/problems/binary-tree-preorder-traversal/
[leetcode 94. Binary Tree Inorder Traversal]: https://leetcode.com/problems/binary-tree-inorder-traversal/