第六章 二叉树**part01**

递归遍历

144. 二叉树的前序遍历

Code :

/**
 * Definition for a binary tree node.
 * 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:
    vector<int> preorderTraversal(TreeNode* root) {
​
        //  数组  /  值   的   传递
​
        vector<int> temp_Vec ;
​
        if(root == NULL)
        {
            return {};
​
        }
​
        /////////////////////
        //  本 结点( 逻辑   __    父结点  所属) 处理 区域
        temp_Vec.push_back(root->val);
​
        ////////////////////
​
        vector<int> temp_Vec_LeftChild = preorderTraversal(root->left);
        vector<int> temp_Vec_RightChild = preorderTraversal(root->right);
​
        // 左右 子树  处理  顺序
​
                                            //注意 左右 子树  处理  顺序
​
        if(!temp_Vec_LeftChild.empty())
        {
            temp_Vec.insert(temp_Vec.end() , temp_Vec_LeftChild.begin() , temp_Vec_LeftChild.end() );
​
        }
​
        if(!temp_Vec_RightChild.empty())
        {
            temp_Vec.insert(temp_Vec.end() , temp_Vec_RightChild.begin() , temp_Vec_RightChild.end() );
​
        }
​
        return temp_Vec ;
    }
};

145. 二叉树的后序遍历

Code :

/**
 * Definition for a binary tree node.
 * 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:
    vector<int> postorderTraversal(TreeNode* root) {
​
        
        //  数组  /  值   的   传递
​
        vector<int> temp_Vec ;
​
        if(root == NULL)
        {
            return {};
​
        }
​
        
​
        vector<int> temp_Vec_LeftChild = postorderTraversal(root->left);
        vector<int> temp_Vec_RightChild = postorderTraversal(root->right);
​
        // 左右 子树  处理  顺序
​
                                            //注意 左右 子树  处理  顺序
​
        if(!temp_Vec_LeftChild.empty())
        {
            temp_Vec.insert(temp_Vec.end() , temp_Vec_LeftChild.begin() , temp_Vec_LeftChild.end() );
​
        }
​
        if(!temp_Vec_RightChild.empty())
        {
            temp_Vec.insert(temp_Vec.end() , temp_Vec_RightChild.begin() , temp_Vec_RightChild.end() );
​
        }
​
        /////////////////////
        //  本 结点( 逻辑   __    父结点  所属) 处理 区域
        temp_Vec.push_back(root->val);
​
        ////////////////////
​
        return temp_Vec ;
​
​
​
    }
};

94. 二叉树的中序遍历

Code :

/**
 * Definition for a binary tree node.
 * 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:
    vector<int> inorderTraversal(TreeNode* root) {
​
        //  数组  /  值   的   传递
​
        vector<int> temp_Vec ;
​
        if(root == NULL)
        {
            return {};
​
        }
​
        
​
        vector<int> temp_Vec_LeftChild = inorderTraversal(root->left);
        vector<int> temp_Vec_RightChild = inorderTraversal(root->right);
​
        // 左右 子树  处理  顺序
​
                                            //注意 左右 子树  处理  顺序
​
        if(!temp_Vec_LeftChild.empty())
        {
            temp_Vec.insert(temp_Vec.end() , temp_Vec_LeftChild.begin() , temp_Vec_LeftChild.end() );
​
        }
​
        /////////////////////
        //  本 结点( 逻辑   __    父结点  所属) 处理 区域
        temp_Vec.push_back(root->val);
​
        ////////////////////
​
        if(!temp_Vec_RightChild.empty())
        {
            temp_Vec.insert(temp_Vec.end() , temp_Vec_RightChild.begin() , temp_Vec_RightChild.end() );
​
        }
​
        
​
        return temp_Vec ;
​
​
    }
};