剑指offer-树相关

树相关

1.重建二叉树

 1 class Solution {
 2 public:
 3     TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
 4         if(pre.size() == 0 || vin.size() == 0)
 5             return nullptr;
 6         return constructCore(pre, vin, 0, pre.size()-1, 0, vin.size()-1);
 7     }
 8     
 9     TreeNode* constructCore(vector<int> pre,vector<int> vin, int sp, int ep, int si, int ei)
10     {
11         //sp, ep 确定先序中树的范围，si，ei确定中序的子树范围
12         //先序头就是根
13         int rootValue = pre[sp];
14         TreeNode* root = new TreeNode(rootValue);
15         if(sp == ep)
16         {
17             if(si == ei && pre[sp] == vin[si])
18                 return root;
19         }
20         //中序找到根，分为左右子树
21         int index = si;
22         while(index <= ei && vin[index] != rootValue)
23             ++index;
24         int leftLen = index-si;//左子树长度
25         if(leftLen > 0)
26         {
27             root->left = constructCore(pre, vin, sp+1, sp+leftLen, si, index-1);
28         }
29         if(leftLen < ep-sp)
30         {
31             root->right = constructCore(pre, vin, sp+leftLen+1, ep, index+1, ei);
32         }
33         return root;
34     }
35 };

2.树的子结构

 1 class Solution {
 2 public:
 3     bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
 4     {
 5         //tree2空或者tree1空都不符合,问清楚空树是不是子树
 6         if(pRoot2 == nullptr || pRoot1 == nullptr)
 7             return false;
 8         bool res = false;
 9         if(pRoot1 != nullptr && pRoot2 != nullptr)
10         {
11             if(pRoot1->val == pRoot2->val)//找到匹配的根
12                 res = isSubTree(pRoot1, pRoot2);
13             if(!res)//未找到，递归左节点
14                 res = HasSubtree(pRoot1->left, pRoot2);
15             if(!res)//未找到，递归节点
16                 res = HasSubtree(pRoot1->right, pRoot2);
17         }
18         return res;
19     }
20     //判断是否是子树
21     bool isSubTree(TreeNode* pRoot1, TreeNode* pRoot2)
22     {
23         //tree2先遍历结束，重合
24         if(pRoot2 == nullptr)
25             return true;
26         //主树先结束，不重合
27         if(pRoot1 == nullptr)
28             return false;
29         //对于节点值不等，不重合
30         if(pRoot1->val != pRoot2->val)
31             return false;
32         
33         //节点值相等，递归判断左右子树
34         return isSubTree(pRoot1->left, pRoot2->left)
35             && isSubTree(pRoot1->right, pRoot2->right);
36     }
37 };

3.二叉树镜像

 1 class Solution {
 2 public:
 3     void Mirror(TreeNode *pRoot) {
 4         //前序遍历（根左右）树每个节点，如果节点有子节点，就交换子节点，直到叶子节点
 5         //处理空树
 6         if(pRoot == nullptr)
 7             return;
 8         //到达叶子节点
 9         if(pRoot->left == nullptr && pRoot->right == nullptr)
10             return;
11         //交换子节点
12         TreeNode* tmp = pRoot->left;
13         pRoot->left = pRoot->right;
14         pRoot->right = tmp;
15         //递归左子树
16         if(pRoot->left)
17             Mirror(pRoot->left);//不要return，因为void不返回
18         
19         //递归右子树
20         if(pRoot->right)
21             Mirror(pRoot->right);
22     }
23 };

4.对称二叉树

 1 class Solution {
 2 public:
 3     bool isSymmetrical(TreeNode* pRoot)
 4     {
 5         return isSymmetrical(pRoot, pRoot);
 6     }
 7     
 8     bool isSymmetrical(TreeNode* pRoot1, TreeNode* pRoot2)
 9     {
10         if(pRoot1 == nullptr && pRoot2 == nullptr)//都空，对称
11             return true;
12         if(pRoot1 == nullptr || pRoot2 == nullptr)//一空一不空。不对称
13             return false;
14         if(pRoot1->val != pRoot2->val)//都不空，值不等，不对称，写了return true就无法再往下遍历了
15             return false;
16         //都不空，且值相等，在比较下一个节点
17         return isSymmetrical(pRoot1->left, pRoot2->right)
18             && isSymmetrical(pRoot1->right, pRoot2->left);
19     }
20 };

5.二叉树前中后续遍历，递归和循环版

递归就是递归，循环实现用栈（前序中序比较简单，后续的话需要简单修改一下前序遍历，反转即可）

前序遍历非递归版

 1 class Solution {
 2 public:
 3     vector<int> res;
 4     vector<int> preorderTraversal(TreeNode *root) {
 5         if(!root)
 6             return {};
 7         stack<TreeNode*> s;
 8         s.push(root);
 9         while(!s.empty())
10         {
11             auto p = s.top();
12             s.pop();
13             res.push_back(p->val);
14             if(p->right)
15                 s.push(p->right);
16             if(p->left)
17                 s.push(p->left);
18         }
19         return res;
20     }
21 };

6.后序遍历非递归版

 1 class Solution {
 2 public:
 3     //一个巧妙地算法，先序遍历:根->左->右，根据出栈顺序根->右->左reverse,变成 左->右->根
 4     vector<int> res;
 5     vector<int> postorderTraversal(TreeNode *root) {
 6         if(root == nullptr)
 7             return {};
 8         stack<TreeNode*> s;
 9         s.push(root);
10         while(!s.empty())
11         {
12             auto p = s.top();
13             s.pop();
14             res.push_back(p->val);
15             if(p->left)
16                 s.push(p->left);
17             if(p->right)
18                 s.push(p->right);
19         }
20         reverse(res.begin(), res.end());
21         return res;
22     }
23 };

7.二叉树中和为某值的路径

 1 class Solution {
 2 public:
 3     vector<vector<int> > res;
 4     //递归解决，防止段错误
 5     vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
 6         if(root == nullptr)
 7             return res;
 8         vector<int> cur;
 9         find(root, expectNumber, cur);
10         return res;
11     }
12     
13     void find(TreeNode* root, int target, vector<int> cur)
14     {
15         if(root == nullptr)
16             return ;
17         cur.push_back(root->val);
18         if((target-root->val) == 0 && root->left == nullptr && root->right == nullptr)
19             res.push_back(cur);
20         else
21         {
22             if(root->left)
23                 find(root->left, target-root->val, cur);
24             if(root->right)
25                 find(root->right, target-root->val, cur);
26         }
27     }
28 };

8.二叉树的深度

（递归）

 1 class Solution {
 2 public:
 3     int res = 0;
 4     int TreeDepth(TreeNode* pRoot)
 5     {
 6         int depth = 0;
 7         getDepth(pRoot, depth);
 8         return res;
 9     }
10     
11     //递归函数，每遇到null节点说明到底了，更新res
12     void getDepth(TreeNode* root, int depth)
13     {
14         if(root == nullptr)
15         {
16             res = (depth > res) ? depth : res;
17             return ;
18         }
19         else
20         {
21            getDepth(root->left, depth+1);
22            getDepth(root->right, depth+1);
23         }
24     }
25 };

非递归（使用队列BFS层序遍历数层数）

class Solution {
public:
    //非递归，使用BFS栈来解决问题,其中的打印内容可以辅助查看具体过程
    int TreeDepth(TreeNode *pRoot)
    {
        if (pRoot == nullptr)
            return 0;
        queue<TreeNode *> s;
        s.push(pRoot);
        int depth = 0;
        while (!s.empty())
        {
            depth++;
            int len = s.size();
            cout << "第" << depth << "层，共有节点：" << len << "个" << endl;
            for (int i = 0; i < len; i++)
            {
                auto p = s.front();
                s.pop();
                cout << p->val << "出栈" << endl;
                if (p->left)
                {
                    s.push(p->left);
                    cout << p->left->val << "入栈" << endl;
                }

                if (p->right)
                {
                    s.push(p->right);
                    cout << p->right->val << "入栈" << endl;
                }
            }
        }
        return depth;
    }
};

9.二叉树的最小深度（使用队列来实现,将上面一个算法简单改改即可：在第一次左右子节点都不存在时，跳出即可）

 1 class Solution {
 2 public:
 3     //那我也用层序遍历(BFS)试试吧
 4     int run1(TreeNode *root) {
 5         if(root == nullptr)
 6             return 0;
 7         
 8         queue<TreeNode*> q;
 9         q.push(root);
10         int depth = 0;
11         while(!q.empty())
12         {
13             depth++;
14             int len = q.size();
15             for(int i=0; i<len; i++)
16             {
17                 auto p = q.front();
18                 q.pop();
19                 if(p->left == nullptr && p->right == nullptr)
20                     return depth;
21                 if(p->left)
22                     q.push(p->left);
23                 if(p->right)
24                     q.push(p->right);
25             }
26         }
27         return depth;
28     }
29     //从上述方法我们可以想到，求算二叉树深度，也可以采用此法，跟我们原来的做法略有不同
30     
31     //神奇的递归做法
32     int run(TreeNode *root) {
33         if(root == nullptr)
34             return 0;
35         int l = run(root->left);
36         int r = run(root->right);
37         if(l == 0 || r == 0)
38             return 1+l+r;
39         else
40             return 1+min(l, r);
41     }
42 };

序列化和反序列化二叉树