letcode 144 二叉树的前序遍历

墨蓝 2022-09-11 06:19 175阅读 0赞

## 前言 ##

题目：[144. 二叉树的前序遍历][144.]

参考题解：[二叉树的递归遍历-代码随想录][-]、[二叉树的迭代遍历-代码随想录][- 1]

--------------------

## 提交代码 ##

题目仅要求遍历。我顺带完成：使用数组存储二叉树；层次遍历建立二叉树；递归/迭代遍历二叉树；删除二叉树。

#include <iostream>
    #include <vector>
    #include <queue>
    #include <stack>
    
    using namespace std;
    
    #define null INT32_MIN  // 使用INT32_MIN代替null
    
    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode() : val(0),left(nullptr),right(nullptr) {}
        TreeNode(int x) : val(x),left(nullptr),right(nullptr) {}
        TreeNode(int x, TreeNode* left, TreeNode* right) : val(x),left(left),right(right) {}
    };
    
    class Solution {
    public:
        // 先序递归遍历二叉树
        void recursive_preorderTraversal(TreeNode* root, vector<int>& result){
            if(root==nullptr) return;
            result.push_back(root->val); // 中
            recursive_preorderTraversal(root->left,result); // 左
            recursive_preorderTraversal(root->right,result); // 右
        }
    
        // 先序迭代遍历二叉树
        void iteration_preorderTraversal(TreeNode* root, vector<int>& result){
            if(root==nullptr)
                return;
            
            result.push_back(root->val);
            stack<TreeNode*> st;
            if(root->right != nullptr) st.push(root->right); // 中左右遍历，所以，先将右边的节点压栈
            if(root->left != nullptr) st.push(root->left);
    
            while(!st.empty()){
                TreeNode* node = st.top();
                st.pop();
                result.push_back(node->val);
                if(node->right != nullptr) st.push(node->right);
                if(node->left != nullptr) st.push(node->left);
            }
        }
    
        vector<int> preorderTraversal(TreeNode* root) {
            vector<int> result;
            // recursive_preorderTraversal(root,result);
            iteration_preorderTraversal(root,result);
            return result;
        }
    };
    
    class Tree{
    private:
        TreeNode* root = nullptr;
    
    public:
        TreeNode* getRoot(){
            return root;
        }
    
        // 层次建立二叉树
        void buildTree(vector<int>& nums){
            const int len = nums.size();
            if(len == 0)
                return;
            
            root = new TreeNode(nums[0]);
            queue<pair<int,TreeNode*>> que; // 存储当前层节点信息：<数组中的下表，对于节点的地址>
            que.push(make_pair(0,root));
    
            while(!que.empty()){ // 层次遍历
                int que_size = que.size(); // 当前层节点个数
                for(int i=0; i<que_size; i++){
                    pair<int,TreeNode*> nodePair = que.front();
                    que.pop();
                    int leftLoc = nodePair.first*2+1;
                    int rightLoc = nodePair.first*2+2;
                    if(leftLoc < len && nums[leftLoc] != null){ // 左节点存在
                        TreeNode* node = new TreeNode(nums[leftLoc]);
                        nodePair.second->left = node;
                        que.push(make_pair(leftLoc,node));
                    }
                    if(rightLoc < len && nums[rightLoc] != null){ // 右节点存在
                        TreeNode* node = new TreeNode(nums[rightLoc]);
                        nodePair.second->right = node;
                        que.push(make_pair(rightLoc,node));
                    }
                }
            }
        }
    
        // 销毁二叉树
        void destroyTree(TreeNode* root){
            if(root!=nullptr){
                destroyTree(root->left);
                destroyTree(root->right);
                delete root;
            }
        }
    
    };
    
    
    int main(void){
        // 构建二叉树
        vector<int> nums = {1,null,2,null,null,3}; 
        Tree tree;
        tree.buildTree(nums);
    
        // 先序遍历二叉树
        Solution s;
        vector<int> result = s.preorderTraversal(tree.getRoot());
        for(auto num : result)
            cout<<num<<" ";
        
        // 销毁二叉树
        tree.destroyTree(tree.getRoot());
    }

[144.]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
[-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.md
[- 1]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.md