剑指offer----树

1. 重建二叉树：根据前序和中序遍历的结果重建二叉树。假设输入的遍历结果都不含有重复的数字。

 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size() == 0){                    //如果为空，返回NULL
            return NULL;
        }
        //依次是前序遍历左子树，前序遍历右子树，中序遍历左子树，中序遍历右子树
        vector<int> left_pre, right_pre, left_vin, right_vin;
        //前序遍历第一个节点一定为根节点
        TreeNode* head = new TreeNode(pre[0]);
        //找到中序遍历的根节点
        int root = 0;
        //遍历找到中序遍历根节点索引值
        for(int i = 0; i < pre.size(); i++){
            if(pre[0] == vin[i]){
                root = i;
                break;
            }
        }
           //利用中序遍历的根节点，对二叉树节点进行归并
        for(int i = 0; i < root; i++){
            left_vin.push_back(vin[i]);
            left_pre.push_back(pre[i + 1]);            //前序遍历第一个为根节点
        }
        
        for(int i = root + 1; i < pre.size(); i++){
            right_vin.push_back(vin[i]);
            right_pre.push_back(pre[i]);
        }
        
        //递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点
        head->left = reConstructBinaryTree(left_pre, left_vin);
        head->right = reConstructBinaryTree(right_pre, right_vin);
        return head;
    }
};

2. 二叉树的下一个节点：给定一颗二叉树和其中的一个节点，如何找到中序遍历序列的下一个节点，每个节点左右子节点指针，还有指向父节点的指针。

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if(!pNode) return nullptr;
        TreeLinkNode* pNext=nullptr;
        //该节点存在右子树，返回右子树的最左叶节点
        if(pNode->right!=nullptr)
        {
            pNext = pNode->right;
            while(pNext->left)
                pNext=pNext->left;
            return pNext;
         //该节点无右子树
        }else if(pNode->next!=nullptr)
        {
            TreeLinkNode* pCurrent=pNode;
            TreeLinkNode* pParent=pNode->next;
            //是否是某父节点的左节点;不是的情况且该节点是某父节点的右子节点，向上递归，直到为某一个父节点的左子节点
            while(pParent!=nullptr && pCurrent==pParent->right)
            {
                pCurrent = pParent;
                pParent = pCurrent->next;
            }
            pNext = pParent;
        }
        return pNext;
    }
};

26. 树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool result=false;
        //非空情况
        if(pRoot1!=nullptr && pRoot2!=nullptr)
        {
            if(pRoot1->val==pRoot2->val)
                result=DoesTree1HaveTree2(pRoot1,pRoot2);
            if(!result)//左右子树上递归
                result=HasSubtree(pRoot1->left,pRoot2);
            if(!result)
                result=HasSubtree(pRoot1->right,pRoot2);
        }
        return result;
    }
private:
    bool DoesTree1HaveTree2(TreeNode* pRoot1,TreeNode* pRoot2)
    {
        if(pRoot2==nullptr)//递归完成返回true
            return true;
        if(pRoot1==nullptr)//未匹配
            return false;
        if(pRoot1->val!=pRoot2->val)
            return false;
        return DoesTree1HaveTree2(pRoot1->left,pRoot2->left) && DoesTree1HaveTree2(pRoot1->right,pRoot2->right);
    }
};

27、二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

• 思路就是左右都是空，就不用管了；而只有一个子节点为空，另一个不为空，也必须交换才行；

class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(!pRoot) return; //Empty tree
        //leaf node already shifted
        if (pRoot->left==nullptr && pRoot->right==nullptr)
            return;
        //whatever empty , both child nodes do shift
        cout << pRoot;
        TreeNode* tmp=pRoot->left;
        pRoot->left=pRoot->right;
        pRoot->right=tmp;
        //recursion
        if(pRoot->left!=nullptr)
            Mirror(pRoot->left);
        if(pRoot->right!=nullptr) 
            Mirror(pRoot->right);
    }
};

28、对称的二叉树

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

• 解题思路：特例：树上的节点值相同的时候还需要比较空节点位置是否对称；
  对称的例子如：

8
6 6
5 7 7 5

class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        return isSymmetrical(pRoot,pRoot);
    }
private:
    bool isSymmetrical(TreeNode* p1, TreeNode* p2)
    {
        if(p1==nullptr && p2==nullptr)
            return true;
        if(p1==nullptr || p2==nullptr)
            return false;
        if(p1->val != p2->val)
            return false;
        return isSymmetrical(p1->left,p2->right) && isSymmetrical(p1->right, p2->left);
    }
};

32、从下到上打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

• 解：层次遍历用队列存储即可。

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

32.2、分行从上到下打印二叉树

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

• 解：需要记录当前层中还没有打印的节点数、下一层节点的数目；

class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int>> ans;
            if(!pRoot) return ans;
            queue<TreeNode*> que;
            que.push(pRoot);
            int nextNodeNum=1;
            while(!que.empty())
            {   
                vector<int> _ans;
                int curNodeNum=nextNodeNum;//当前层的数目为1，下一层的数目节点为0
                nextNodeNum=0;
                while(curNodeNum)
                {
                    TreeNode* top=que.front();
                    _ans.push_back(top->val);
                    if(top->left)
                    {
                        que.push(top->left);
                        nextNodeNum++;
                    }
                    if(top->right)
                    {
                        que.push(top->right);
                        nextNodeNum++;
                    }
                    que.pop();
                    --curNodeNum;
                }
                ans.push_back(_ans);
            }
            return ans;
        }
};

33、二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

• 解析：最末的位置存储的是根节点，然后左右子树的边界通过循环可以找到，进一步判断右子树是否都小于根节点，如果满足，下一步看左右子树若存在，左右子树是否递归满足。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        return Help(sequence, sequence.size());
    }
private:
    bool Help(const vector<int> &sequence, int size)
    /*
    Params:size represents the root node position.
    */
    {
        if(sequence.empty()) return false;
        int i=0;
        //找寻左右子树分界节点
        for(;i<size-1;++i)
            if(sequence[i]>sequence[size-1])
                break;
        //右子树是否满足大于根节点
        for(int j=i;j<size;++j)
            if(sequence[j]<sequence[size-1])
                return false;
        //递归判断左子树
        bool left=true;
        if(i>0)//存在左子树才行
            left = Help(sequence, i);
        bool right=true;
        if(i<size-1)
            right=Help(sequence, size-1);
        return left && right;
    }
};

34、二叉树中和为某一值的路径

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

• 解析：
  方法1. 递归、判断成功的时候把成功的路径压入结果ans；但是每次递归path需要重新拷贝使用；
  方法2.

class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> ans;
        vector<int> path;
        if(!root) return ans;
        _FindPath(root,expectNumber,path,ans);
        return ans;
    }
private:
    //path不能用引用，递归的时候需要拷贝path
    void _FindPath(TreeNode* root,int num, vector<int> path, vector<vector<int>> &ans)
    {
        if(root)
        {
            path.push_back(root->val);
            if(num==root->val && (!root->left) && (!root->right))
            {    
                ans.push_back(path);
                return;
            }
            _FindPath(root->left,num - root->val, path, ans);
            _FindPath(root->right,num - root->val, path, ans);
        }
    }
};

36、二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

• 递归，根节点进入，然后向左递归，出来之后，若有右节点，向右走，走到none在指向root，root在指向它；右子树也一样这样。

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==nullptr) return nullptr;
        pRootOfTree=ConvertNode(pRootOfTree);
        while(pRootOfTree->left) pRootOfTree=pRootOfTree->left;
        return pRootOfTree;
    }
private:
    //返回子树的根节点
    TreeNode* ConvertNode(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==nullptr) return nullptr;
        if(pRootOfTree->left!=nullptr)
        {   
            TreeNode* left = ConvertNode(pRootOfTree->left);
            //左子树的根节点往右走、它的下一个节点是当前的根节点
            while(left->right) left=left->right;
            left->right=pRootOfTree;
            pRootOfTree->left=left;
        }
        if(pRootOfTree->right!=nullptr)
        {
            TreeNode* right = ConvertNode(pRootOfTree->right);
            //右子树的根节点往左走、它的上一个节点是目前的根节点；
            while(right->left) right=right->left;
            right->left=pRootOfTree;
            pRootOfTree->right=right;
        }
        return pRootOfTree;
    }
};

37、序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

• 不太熟悉char的这些操作，看别人的答案，非得搞指针传入的默认函数。

class Solution {
public:
    char* Serialize(TreeNode *root) {    
        if(!root) return "#";
        string r = to_string(root->val);
        r.push_back(',');
        char *left = Serialize(root->left);
        char *right = Serialize(root->right);
        char *ret = new char[strlen(left) + strlen(right) + r.size()];
        strcpy(ret, r.c_str());
        strcat(ret, left);
        strcat(ret, right);
        return ret;
    }
    TreeNode* Deserialize(char *str) {
        return decode(str);
    }
private:
    TreeNode* decode(char* &str)
    {
        if(*str=='#')
        {
            str++;
            return nullptr;
        }
        int num=0;
        while(*str != ',') //每一个值都是char
            num = num*10 + (*(str++)-'0');
        str++;
        TreeNode* root=new TreeNode(num);
        root->left = decode(str);
        root->right = decode(str);
        return root;
    }
};

54、

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

• //思路：二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。
  // 所以，按照中序遍历顺序找到第k个结点就是结果。

class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(pRoot== nullptr || k==0)
            return nullptr;
        return findKthNode(pRoot, k);
    }
private:
    TreeNode* findKthNode(TreeNode* pRoot, int &k)
    {
        TreeNode* target = nullptr;
        if(pRoot->left!=nullptr)
            target = findKthNode(pRoot->left, k);
        if(target == nullptr)
        {
            if(k==1)
                target = pRoot;
            k--;
        }
        if(target==nullptr && pRoot->right!=nullptr)
            target = findKthNode(pRoot->right, k);
        return target;
    }
};

class Solution {
public:
    int index = 0;
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(pRoot!=nullptr)
        {
            TreeNode* node =  KthNode(pRoot->left, k);
            if(node!=nullptr) 
                return node;
            index++;    //中序遍历操作处
            if(index==k)
                return pRoot;
            node = KthNode(pRoot->right, k);
            if(node!=nullptr)
                return node;
        }
        return nullptr;
    }
};

55、输入一棵二叉树，求该树的深度。

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

class Solution {
public:
    //二叉树的深度为从根节点到叶节点的最长路径长度;
    //如果只有根节点，那么树的深度是1;
    //如果有左右子树，那么树的深度为左子树与右子树中最大的深度+1;
    int TreeDepth(TreeNode* pRoot)
    {
        if(pRoot==nullptr)
            return 0;
        int left = TreeDepth(pRoot->left);
        int right = TreeDepth(pRoot->right);
        return 1+ max(left, right);
    }
};

55.2、输入一棵二叉树，判断该二叉树是否是平衡二叉树。

如果某二叉树中任意节点的左、右子树的深度相差不超过1，那么他就是一颗平衡二叉树。

• 方法1：求节点的左右子树的深度，然后判断是否相差不大于1；
  方法2：由于方法1中重复的遍历了某些节点，因此我们选择后序遍历每一个节点，这样的话在遍历一个节点之前，
  已经遍历了它的左、右子树；遍历的同时记录节点深度；

class Solution {
public:
    /*
    方法1：求节点的左右子树的深度，然后判断是否相差不大于1；
    */
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot==nullptr)
            return true;
        int left = TreeDepth(pRoot->left);
        int right = TreeDepth(pRoot->right);
        int diff = left - right;
        if(diff<-1 || diff>1)
            return false;
        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
    }
private:
    int TreeDepth(TreeNode* root)
    {
        if(root==nullptr)
            return 0;
        int left = TreeDepth(root->left);
        int right = TreeDepth(root->right);
        return 1+max(left,right);
    }
};

class Solution {
public:
    /*
    方法1：求节点的左右子树的深度，然后判断是否相差不大于1；
    方法2：由于方法1中重复的遍历了某些节点，因此我们选择后序遍历每一个节点，这样的话在遍历一个节点之前，
    已经遍历了它的左、右子树；遍历的同时记录节点深度；
    */
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int depth = 0;
        return IsBalanced(pRoot, depth);
    }
private:
    bool IsBalanced(TreeNode* pRoot, int &depth)
    {
        if(pRoot == nullptr)
        {
            depth=0;
            return true;
        }
        int left, right;
        if(IsBalanced(pRoot->left, left) && IsBalanced(pRoot->right, right))
        {
            int diff = left - right;
            if(diff <= 1 && diff >=-1)
            {
                depth = 1 + (left>right ?left :right);
                return true;
            }
        }
        return false;
    }
};

按之字形打印树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

• 1.队列+数组翻转来实现，偶数的时候翻转数组再添加；2.双栈实现

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        if(pRoot==nullptr) return vector<vector<int> >();
        queue<TreeNode*> que;
        vector<vector<int>> ans;
        que.push(pRoot);
        bool even = false; //偶数的时候翻转数组
        while(!que.empty())
        {
            vector<int> _ans;
            int size=que.size();
            for(int i=0;i<size;++i) //打印完当前行的元素
            {
                TreeNode* front = que.front();
                _ans.push_back(front->val);
                que.pop();
                if(front->left!=nullptr)
                    que.push(front->left);
                if(front->right!=nullptr)
                    que.push(front->right);
            }
            if (even)
            {
                reverse(_ans.begin(),_ans.end());
            }
            even = !even;
            ans.push_back(_ans);
        }
        return ans;
    }
    
};