专题复习：二叉树（1）

（1）最基本的二叉树的 先序 中序 后序遍历

//先序遍历
void preOrder(ListNode* root)
{
   if(!root) return;
   cout << root->val <<endl;
   preOrder(root->left);
   preOrder(root->right);
}

//中序遍历
void medOrder(ListNode *root)
{
    if(!root) return;
    medOrder(root->left);
    cout << root->val << endl;
    medOrder(root->right);
}

//后序遍历

void postOrder(ListNode *root)
{
   if(!root) return;
   postOrder(root->left);
   postOrder(root->right);
   cout<< root->val << endl;
}
           

(2) 剑指 Offer 07. 重建二叉树

//root 表示在前序遍历中的root的位置

    // left 表示 前序遍历中root节点 在中序遍历中 对应的左子树边界

    //right 表示 前序遍历中root节点 在中序遍历中 对应的右子树边界

unordered_map<int, int> inorderIndex;
class Solution {
    TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int root, int left, int right)
    {
        if(left > right) return NULL;
        int rootIndexInInorder = inorderIndex[preorder[root]];
        int leftTreeSize = rootIndexInInorder - left;
        TreeNode* t = new TreeNode(preorder[root]);
        t->left = dfs(preorder, inorder, root + 1, left, rootIndexInInorder - 1);
        t->right = dfs(preorder , inorder, root + 1 + leftTreeSize,rootIndexInInorder + 1,right);
        return t;
    } 
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0) return NULL;
        for(int i = 0; i < inorder.size(); i++)
        {
            inorderIndex[inorder[i]] = i;
        }
        TreeNode *root = dfs(preorder, inorder, 0 , 0, inorder.size() - 1);
        return root;
    }
};
           

剑指 Offer 33. 二叉搜索树的后序遍历序列

思路：利用递归 将原树分割为左子树和右子树

helper(poster, left , right)  left 和 right分别表示 子树中所有节点在poster数组中 所占的索引范围

class Solution {

    bool helper(vector<int> &postorder, int left, int right)
    {
        if(left > right) return true;
        int root = postorder[right];
        int med = left;//找打左子树 和 右子树的分割线
        while(postorder[med] < root)
        {
            med++;
        }
        int temp = med;
        while( temp < right)
        {
            if(postorder[temp++] < root) return false;
        }
        //将原树 分隔为左子树和右子树
        return helper(postorder, left, med - 1)&& helper(postorder , med, right - 1);
    }
public:
    bool verifyPostorder(vector<int>& postorder) {
        //后序遍历的顺序是 左 右  中
        int size = postorder.size();
        if(size == 0) return true;
        return helper(postorder, 0, size - 1);

    }
};
           

剑指 Offer 32 - I. 从上到下打印二叉树

思路：利用队列先入先出  利用辅助队列的，基本都是BFS的方法

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        queue<TreeNode*> a;
        a.push(root);
        while(!a.empty())
        {
            TreeNode * temp = a.front();
            a.pop();
            res.push_back(temp->val);
            if(temp->left) a.push(temp->left);
            if(temp->right) a.push(temp->right);
        }
        return res;

    }
};
           

剑指 Offer 32 - II. 从上到下打印二叉树 II

在上一题的基础上，利用queue.size()

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
         vector<vector<int>> res;
         if(!root) return res;
         queue<TreeNode*> a;
         a.push(root);
         while(!a.empty())
         {
             int len = a.size();
             vector<int> temp;
             while(len--)
             {
                 TreeNode *t = a.front();
                 a.pop();
                 temp.push_back(t->val);
                 if(t->left) a.push(t->left);
                 if(t->right) a.push(t->right);
             }
             res.push_back(temp);
         }
         return res;
    }
};
           

剑指 Offer 28. 对称的二叉树

方法一：利用递归

class Solution {
    bool helper(TreeNode *left, TreeNode *right)
    {
        if(!left && !right) return true;
        if(!left || !right || left->val != right->val) return false;
        return helper(left->left, right->right) && helper(left->right, right->left);
    }
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return helper(root->left, root->right);
    }
};
           

方法二：非递归，利用队列 先将节点按对称的顺序存入队列中，然后 每次取两个来比较

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode*> a;
        a.push(root->left);
        a.push(root->right);
        while(!a.empty())
        {
            TreeNode *left = a.front();
            a.pop();
            TreeNode *right = a.front();
            a.pop();
            if(!left && !right) continue;
            if(!left || !right || left->val!= right->val) return false;
            a.push(left->left);
            a.push(right->right);
            a.push(left->right);
            a.push(right->left);
        }
        return true;
    }
};