Cybay
0%

二叉树

发表于 更新于 分类于 Valine：
二叉树
1
2
3
4
5
6
7
8
9
10
// 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) {}
};

一、遍历

深度优先遍历

递归遍历

前序遍历
1
2
3
4
5
6
7
void traversal(TreeNode* cur,vector<int>& v)
    {
        if(!cur) return;
        v.push_back(cur->val);
        traversal(cur->left,v);
        traversal(cur->right,v);
    }
中序遍历
1
2
3
4
5
6
7
void traversal(TreeNode* cur,vector<int>& v)
    {
        if(!cur) return;
        traversal(cur->left,v);
    	v.push_back(cur->val);
        traversal(cur->right,v);
    }
后序遍历
1
2
3
4
5
6
7
void traversal(TreeNode* cur,vector<int>& v)
    {
        if(!cur) return;
        traversal(cur->left,v);
        traversal(cur->right,v);
    	v.push_back(cur->val);
    }

迭代遍历

前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if(!root) return result;
        stack<TreeNode*> st;
        st.push(root);
        
        while(!st.empty())
        {
            TreeNode* cur = st.top();
            result.push_back(cur->val);
            st.pop();
            if(cur->right) st.push(cur->right);
            if(cur->left) st.push(cur->left);
        }

        return result;
    }
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        auto cur=root;
        while(!st.empty()||cur)
        {
            if(cur!=nullptr)
            {
                st.push(cur);
                cur=cur->left;
            }
            else 
            {
                cur=st.top();
                st.pop();
                result.push_back(cur->val);
                cur=cur->right;
            }
        }
        return result;
    }
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if(!root) return result;
        stack<TreeNode*> st;
        st.push(root);
        
        while(!st.empty())
        {
            TreeNode* cur=st.top();
            result.push_back(cur->val);
            st.pop();
            if(cur->left) st.push(cur->left);
            if(cur->right) st.push(cur->right);
        }
		reverse(result.begin(),result.end());
        return result;
    }

广度优先遍历(层序遍历)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> > result;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            int n=que.size();
            vector<int> vec;
            
            for(int i=0;i<n;++i)
            {
                auto t=que.front();
                que.pop();
                if(t->left) que.push(t->left);
                if(t->right) que.push(t->right);
                vec.push_back(t->val);
            }
            result.push_back(vec);
        }
        return result;
    }
};

二、常见操作

反转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        invert(root);
        return root;
    }
    void invert(TreeNode* cur)
    {
        if(!cur) return;
        std::swap(cur->left,cur->right);
        rev(cur->left);
        rev(cur->right);
    }
};

判断是否对称

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return compare(root->left, root->right);
    }
    bool compare(TreeNode* t1, TreeNode* t2)
    {
        if(t1 && !t2) return false;
        if(!t1 && t2) return false;
        if(!t1 && !t2) return true;
        if(t1->val != t2->val) return false;
        //注意要比较的节点
        return compare(t1->left, t2->right) && compare(t1->right,t2->left);
    }
};

求深度

最大深度
1
2
3
4
5
6
7
8
9
10
int maxDepth(TreeNode* root) {
        return getDepth(root);
    }
    int getDepth(TreeNode* node)
    {
        if(!node) return 0;
        int t1=getDepth(node->left);  //左子树高度
        int t2=getDepth(node->right); //右子树高度
        return max(t1,t2)+1;
    }
最小深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int minDepth(TreeNode* root) {
        return getMin(root);
    }
    int getMin(TreeNode* node)
    {
        if(!node) return 0;
        int leftdepth=getMin(node->left);
        int rightdepth=getMin(node->right);
        //处理左右节点为空的情况
        if(!node->left&&node->right)
            return 1+rightdepth;
        if(node->left&&!node->right)
            return 1+leftdepth;
        return 1+min(leftdepth,rightdepth);
    }

判断平衡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isBalanced(TreeNode* root) {
    return isb(root)==-1?0:1;
}
int isBalanced(TreeNode* node)
{
    if(node==nullptr) return 0;
    int left=isBalanced(node->left);
    if(left==-1) return -1;
    int right=isBalanced(node->right);
    if(right==-1) return -1;
    //返回-1表示终止
    if(abs(left-right)>1) return -1;
    return 1+max(left,right);
}

构造二叉树

前序与中序遍历构造
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(inorder.empty()) return nullptr;
        return tra(preorder, 0, preorder.size(), inorder, 0, inorder.size());
    }
    TreeNode* tra(vector<int>& preorder, int preBegin, int preEnd,
    vector<int>& inorder, int inBegin, int inEnd)
    {
        if(preBegin == preEnd) return nullptr;
        
        //切割区间左闭右开
        
        //当前节点数值为前序数组首项
        int val = preorder[preBegin];
        TreeNode* root = new TreeNode(val);
        if(preEnd-preBegin == 1) return root;
        
        int i;
        for(i = inBegin; i < inEnd; ++i)
            if(inorder[i] == val) break;
        
        //切分中序
        int inBeginleft = inBegin, inEndleft = i;
        int inBeginright = 1 + i, inEndright = inEnd;
		
        //切分前序
        int preBeginleft = 1 + preBegin;
        int preEndleft = preBeginleft + inEndleft - inBeginleft;
        int preBeginright = preEndleft;
        int preEndright = preEnd;
        
        root->left = tra(preorder, preBeginleft, preEndleft, inorder,
                       inBeginleft, inEndleft);
        root>right = tra(preorder, preBeginright, preEndright,
                       inorder, inBeginright, inEndright);
        
        return root;
    }
中序与后序遍历构造
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.empty()) return nullptr;
        return build(inorder, 0, inorder.size(), 
        postorder, 0, postorder.size());
    }
    TreeNode* build(vector<int>& inorder, int inBegin, int inEnd,
    vector<int>& postorder, int poBegin, int poEnd)
    {
        if(poBegin == poEnd) return nullptr;
        
        //切割区间左闭右开
        
        //当前节点数值为后序数组末项
        int val = postorder[poEnd - 1];
        TreeNode* root = new TreeNode(val);
        if(poEnd - poBegin == 1) return root;//仅有一项，为叶，返回

        int target;//搜索左右子树分界点
        for(target = inBegin; target < inEnd; ++target)
            if(inorder[target] == val) 
                break;
        
        //切分中序
        int leftinBegin = inBegin, leftinEnd = target;
        int righrinBegin = target + 1, rightinEnd = inEnd;
        
        //切分后续
        int leftpoBegin = poBegin, leftpoEnd = poBegin + target - inBegin;
        int rightpoBegin = leftpoEnd, rightpoEnd = poEnd - 1;

        root->left = build(inorder, leftinBegin, leftinEnd,
        postorder,leftpoBegin, leftpoEnd);

        root->right = build(inorder, righrinBegin, rightinEnd,
        postorder, rightpoBegin, rightpoEnd);

        return root;
    }

三、二叉搜索树

搜索

1
2
3
4
5
TreeNode* searchBST(TreeNode* root, int val) {
        if(root == nullptr || root->val == val) return root;
        if(root->val>val) return searchBST(root->left, val);
        return searchBST(root->right, val);
    }

判断是否为二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
//中序遍历二叉搜索树，节点数值递增
class Solution {
public:
    TreeNode* pre = nullptr;
    bool isValidBST(TreeNode* root) {
        if(!root) return true;    
        bool b1 = isValidBST(root->left);
        if(pre && pre->val >= root->val) return false;
        pre = root;
        bool b2 = isValidBST(root->right);
        return b1 && b2;
    }
};

求众数的集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:

    vector<int> result;
    int maxcount;
    int count;
    TreeNode* pre;
    vector<int> findMode(TreeNode* root) {
        maxcount = 0;
        count = 1;
        pre = nullptr;
        ser(root);
        return result;
    }
    void ser(TreeNode* node)
    {
        if(!node) return;
        ser(node->left);
        if(pre) if(pre->val == node->val)
                    ++count;
                else count = 1;
        if(count > maxcount)
        {
            maxcount = count;
            result.clear();
            result.push_back(node->val);
        }
        else if(count == maxcount)
        result.push_back(node->val);
        pre = node;
        ser(node->right);
    }
};