二叉树

查找二叉树中最大的搜索二叉树拓扑结构

//暴力解法
//1. 问题描述：存在的最大的二叉树拓扑结构，假定数据不会重复
    public boolean check(Node node,int value){
        if (node==null)
            return false;
        if (node.val==value)
            return true;
        else if (node.val>value)    //往左搜索
            return check(node.left,value);
        else    //往右搜索
            return check(node.right,value);
    }
//2.先序遍历搜集最大拓扑结构
public int search(Node head,Node node){
        int i=0;
        if (node==null)
            return 0;
        if (check(head,node.val))
            i++;
        int left=search(head,node.left);   //左子树
        int right=search(head,node.right); //右子树
        return left+right+i;
    }
//3.*搜索全部结点,最大的拓扑结构的首结点
    int max;
    Node node1;
    public void query(Node node){
        if (node==null)
            return;
        int i=search(node,node);
        if (max<i) {
            max = i;
            node1=node;
        }
        query(node.left);
        query(node.right);
    }

// 左成云解法
1.整个过程使用后序遍历
2.遍历到当前节点记为cur时，先遍历cur的左子树收集4个信息，
分别是左子树上最大搜索二叉子树的头节点(lBST)、节点数(lSize)、
最小值(lMin)和最大值(lMax)。再遍历cur的右子树收集4个信息，
分别是右子树上最大搜索二叉子树的头节点(rBST)、节点数(rSize)、
最小值(rMin)和最大值(rMax)
3.根据步骤2所收集的信息，判断是否满足搜索子树的定义，
如果满足就返回cur节点，如果不满足就返回lBST和rBST中节点数多的那一个

public Node biggestSubBST(Node head) {
        int[] record = new int[3];
        return posOrder(head, record);
    }
    
    public Node posOrder(Node head, int[] record) {
        if (head == null) {
            record[0] = 0;
            record[1] = Integer.MAX_VALUE;
            record[2] = Integer.MIN_VALUE;
            return null;
        }
        int value = head.value;
        Node left = head.left;
        Node right = head.right;
        Node lBST = posOrder(left, record);
        int lSize = record[0];
        int lMin = record[1];   //记录左边最小值
        int lMax = record[2];  //记录左边最大值
        Node rBST = posOrder(right, record);
        int rSize = record[0];
        int rMin = record[1];
        int rMax = record[2];
        
        record[1] = Math.min(lMin, value);
        record[2] = Math.max(rMax, value);
        
        if (left == lBST && right == rBST && lMax < value && value < rMin) {
            record[0] = lSize + rSize + 1;
            return head;
        }
        
        record[0] = Math.max(lSize, rSize);
        return lSize > rSize ? lBST : rBST;
    }

96.不同的二叉搜索树
给定n，求可以构成多少种二叉搜索树

dp(n)=dp(0)dp(n-1)+dp(1)dp(n-2)+dp(2)dp(n-3)+…+dp(n-1)dp(0)

95. 不同的二叉搜索树 II
给定n，返回可以构成的搜索二叉树; 这里使用了函数指针
102.二叉树的层次遍历
queue,需要按层打印则需要两外维护两个TreeNode，last和nlast

 vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == NULL) return {};
        queue<TreeNode*> q;
        vector<vector<int> > result;
        vector<int> tmp;
        q.push(root);
        TreeNode* last=root;
        TreeNode* nlast=root;
        while(!q.empty()){
            TreeNode *t = q.front();
            q.pop();
            tmp.push_back(t->val);
            if (t->left != NULL){
                q.push(t->left);
                nlast=t->left;           
            }
            if (t->right != NULL){
                q.push(t->right);
                nlast=t->right;
            }
            if (last == t){
                result.push_back(tmp);
                tmp.clear();
                last=nlast;
            }
        }
        return result;
    }

107. 二叉树的层次遍历 II
反向打印，只需要把result.push_back()改成result.insert()即可
103. 二叉树的锯齿形层次遍历
queue,需要维护一个change，表示是否需要反转

 vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> result;
        queue<TreeNode*> q;
        q.push(root);
        bool change = false;
        while(!q.empty()){
            int n = q.size();
            vector<int> res;
            while(n--){
                TreeNode* tmp=q.front();
                q.pop();  
                res.push_back(tmp->val);
                if(tmp->left != NULL) q.push(tmp->left);
                if(tmp->right != NULL) q.push(tmp->right);
            }
            if(change){
                result.push_back(vector<int>(res.rbegin(), res.rend()));
            }else{
                result.push_back(res);
            }
            change = !change;
        }
        return result;
    }

二叉树后序非递归

void postorderTraversalNew(TreeNode *root, vector<int> &path)
{
    stack< pair<TreeNode *, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty())
    {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == NULL)
            continue;
        if(visited)
        {
            path.push_back(root->val);
        }
        else
        {
            s.push(make_pair(root, true));
            s.push(make_pair(root->right, false));
            s.push(make_pair(root->left, false));
        }
    }
}

树的子结构

public boolean HasSubtree(TreeNode root1, TreeNode root2) {   
        boolean result = false;
        if(root1 != null && root2 != null) {   
            if(root1.val == root2.val) {
                result = judge(root1, root2);
            }
            if(!result) {
                result = HasSubtree(root1.left, root2);
            }
            if(!result) {
                result = HasSubtree(root1.right, root2);
            }
        }
        return result;
    }
    private boolean judge(TreeNode root1, TreeNode root2) {      
        if(root2 == null)
            return true;
        if(root1 == null)
            return false;
        if(root1.val != root2.val)
            return false;
        return judge(root1.left, root2.left) && judge(root1.right, root2.right);
    }

前序中序构造二叉树

TreeNode *buildTree(vector<int> &pre, vector<int> &in) {
        if (pre.size() == 0) return NULL;
        return build(pre, in , 0, pre.size()-1, 0, in.size()-1);
    }
    TreeNode *build(vector<int> &pre,vector<int> &in,int startpre,int endpre,int startin,int endin) {
        if (startpre > endpre || startin > endin) return NULL;
        TreeNode *root = new TreeNode(pre[startpre]);
        int divide = 0;
        while (divide <= endin && in[divide] != root->val) divide++;
        int offset = divide - startin - 1;
        root->left = build(pre, in, startpre + 1, startpre + 1 + offset, startin, startin + offset);
        root->right = build(pre, in, startpre + offset + 2, endpre, divide + 1,endin);
        return root;
    }

二叉搜索树转成双向链表

image.png

 TreeNode* convert(TreeNode* root) {
        if (!root) return root;
        stack<TreeNode*> st;
        while (root){
            st.push(root);
            root = root->left;
        }
        TreeNode* ans = st.top();
        TreeNode* last = NULL;
        while (!st.empty()){
            TreeNode* tmp = st.top();
            st.pop();
            if (!last) last = tmp;
            else {
                last->right = tmp;
                tmp->left = last;
                last = tmp;
            }
            tmp = tmp->right;
            while (tmp){
                st.push(tmp);
                tmp = tmp->left;
            }
        }
        return ans;
    }


void Convert(BiNode<Type> *root, BiNode<Type> *& last)
{
    if(root == NULL)
        return;
    Convert(root->left, last);
    root->left = last;
    if(last != NULL)
        last->right = root;
    last = root;
    Convert(root->right, last);
}
 
BiNode<Type> * Convert2BinLink( BiNode<Type> *root )
{
    if(root == NULL)    
        return NULL;
    BiNode<Type> * last = NULL;
    //二叉排序树转换成排序双向链表
    Convert(root, last);
    //取得双向链表的头指针
    while(root->left != NULL)
        root = root->left;
    return root;
}

二叉搜索树的插入

 TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == NULL) {
            return new TreeNode(val);
        }
        if(val < root->val) {
            root->left = insertIntoBST(root->left, val);
        } else {
            root->right = insertIntoBST(root->right, val);
        }
        return root;
    }