二叉树与分治法_加权二叉树

作者：不正经 | 2024-02-14 22:08:03

踩

加权二叉树

二叉树与分治算法

1、二叉树深度：O(log(n))~O(n)。
2、是否使用递归要看递归的深度，太深容易出现Stackoverflow的问题。
3、二叉树大部分情况下可能会考递归，当然也可能会出现考非递归的情况（迭代）。

一、时间复杂度训练

1、通过O(n)的时间，把n的问题变成两个n/2的问题，复杂度是多少？
求解：
方法一、
先写T(n)的表达式：
T(n) = 2T(n/2) + O(n) = 2T(2T(n/2) + O(n/2)) + O(n) = 4T(n/2) + 2O(n) = ... = n(T(1)) + O(nlog(n)) = O(n) + O(nlog(n)) = O(nlog(n))
方法二、树形分析法：
在这里插入图片描述

这种复杂度的算法有：归并排序，快速排序（最好的情况下）
2、通过O(1)的时间，把n的问题变成两个n/2的问题，复杂度是多少？
方法一、

T(n) = 2T(n/2) + O(1) = ... = O(n)
1

方法二、树形分析法：
在这里插入图片描述

二、思路

碰到二叉树的问题，就想想我要在整个二叉树上得到的结果，和我在左子树得到的结果和我在右子树上得到的结果有什么关系。（比如说整棵树上要求一个什么东西，我先不去求整个棵树，我先求出左子树是什么样，再求出右子树什么样，在研究整颗树要求的结果，和左子树结果与右子树结果，还有根的关系是什么）

三、二叉树的遍历：

在这里插入图片描述

（1）递归实现1（遍历方式）：
1>递归四要素：1.递归的定义；2.递归的拆解；3.递归的出口；4.递归的调用。
这种实现方式，定义了一个全局变量，然后每次遍历都把结果装到这个全局的盒子里。它的递归函数没有返回值（返回值为void）
（2）递归实现2（分治方式）
这种方式，每次递归的时候都新建一个变量，然后左子树得到一个该变量的值，右子树也得到一个该变量的值，最后它俩拼出一个新的变量值作为结果。它的递归函数是有返回值的，也就是每次调用它都会有一个局部解（如果前序遍历的话，会是某个子树的前序遍历）。

1、前序遍历
题目链接：http://www.lintcode.com/problem/binary-tree-preorder-traversal/
2、前序遍历代码

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
//递归版本（遍历方式）
class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Preorder in ArrayList which contains node values.
     */
    //递归的定义
    void traverse(TreeNode *root, vector<int> *result)
    {
        //递归的出口
        if(root == NULL)
        {
            return;
        }
        
        //递归的拆解
        (*result).push_back(root->val);
        traverse(root->left, result);
        traverse(root->right, result);
    }
     
    vector<int> preorderTraversal(TreeNode * root) {
        vector<int> *result;
        //递归的调用
        traverse(root, result);
        return *result;
    }
};

//递归版本（分治方法）
class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Preorder in ArrayList which contains node values.
     */
    vector<int> preorderTraversal(TreeNode * root) {
        vector<int> result;
        
        //递归的出口
        if(root == NULL)
        {
            return result;
        }
        
        //递归的拆解（分治）
        vector<int> left = preorderTraversal(root->left);
        vector<int> right = preorderTraversal(root->right);
        
        //合并
        result.push_back(root->val);
        for(auto i : left)
            result.push_back(i);
        for(auto i : right)
            result.push_back(i);
        
        return result;
    }
};

//非递归版本
class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Preorder in ArrayList which contains node values.
     */
    vector<int> preorderTraversal(TreeNode * root) {
        vector<int> preorder = {};
        stack<TreeNode *> Stack;
        
        if(root == NULL){
            return preorder;
        }
        Stack.push(root);
        while(!Stack.empty()){
        	//将遍历结果存入preorder
            TreeNode* node = Stack.top();
            Stack.pop();
            preorder.push_back(node->val);
			
			//更新栈Stack
            if(node->right){
                Stack.push(node->right);
            }
            if(node->left){
                Stack.push(node->left);
            }
        }
        return preorder;
    }
};
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

3、中序遍历和后序遍历递归的实现方法与前序遍历相似，只是遍历的顺序不同而已。但非递归的方法有些不同：
（1）中序遍历：中序遍历需要先一边找到最左边root=root->left，一边将root压入栈Stack中，然后再进行遍历输出和更新栈。
题目链接：https://www.lintcode.com/problem/binary-tree-inorder-traversal/description

class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Inorder in ArrayList which contains node values.
     */
    //递归的定义
    /*void Traversal(TreeNode *Node, vector<int> *inorder){
        //递归的出口
        if(Node == NULL){
            return;
        }
        
        //递归的拆解
        Traversal(Node->left, inorder);
        (*inorder).push_back(Node->val);
        Traversal(Node->right, inorder);
    }*/
    vector<int> inorderTraversal(TreeNode * root) {
       /* //1、Traversal方法
        vector<int> *inorder;
        //递归的调用
        Traversal(root, inorder);
        return *inorder;
        */
        
        /*//2、分治算法
        vector<int> inorder = {};
        if(root == NULL){
            return inorder;
        }
        //递归的拆解,分治
        vector<int> left = inorderTraversal(root->left);
        vector<int> right = inorderTraversal(root->right);
        
        //合并
        for (auto i : left)
            inorder.push_back(i);
        inorder.push_back(root->val);
        for (auto i : right)
            inorder.push_back(i);
        
        return inorder;*/
        
        //3、非递归方法
        vector<int> inorder = {};
        stack<TreeNode *> Stack;
        while (root != NULL){
            Stack.push(root);
            root = root->left;
        }
        /**     1
               / \
              2   3
             /   / \
            2   3   4
           / \
          3   4
             / \
            2   3
        */
        
        while (!Stack.empty()){
            //将遍历存到结果(inorder)中
            TreeNode *Node = Stack.top();
            inorder.push_back(Node->val);
            
            //更新Stack            
            if (Node->right == NULL)
            {
                Node = Stack.top();
                Stack.pop();
                while(!Stack.empty() && Stack.top()->right == Node){
                    Node = Stack.top();
                    Stack.pop();
                    
                }
            }
            else
            {
                Node = Node->right;
                while(Node != NULL){
                    Stack.push(Node);
                    Node = Node->left;
                }
            }
        }
        return inorder;
    }
};
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

（2）后序遍历：后序遍历代码实现时，边找最左边和最右边的节点，边更新栈和输出结果。
题目链接：http://www.jiuzhang.com/solutions/binary-tree-postorder-traversal/
代码实现：使用栈进行二叉树后序遍历，首先对左子树进行遍历压入栈中，直至左子树为空，然后访问右子树。故每个节点会被访问两次，当节点被第二次访问时，即curr->right=lastvisit时，该节点出栈。

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

// //递归的定义
// void Traversal(TreeNode *root, vector<int> *postorder)
// {
//     //递归的出口
//     if(root == NULL){
//         return;
//     }
    
//     //递归的拆解
//     Traversal(root->left, postorder);
//     Traversal(root->right, postorder);
//     (*postorder).push_back(root->val);
// }

class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Postorder in ArrayList which contains node values.
     */
    vector<int> postorderTraversal(TreeNode * root) {
        // //1、Traversal方法
        // vector<int> *postorder;
        // //递归的调用
        // Traversal(root, postorder);
        // return *postorder;
        
        /*//2、分治算法
        vector<int> postorder;
        
        //递归的出口
        if(root == NULL)
        {
            return {};
        }
        //分治
        vector<int> left = postorderTraversal(root->left);
        vector<int> right = postorderTraversal(root->right);
        
        //合并
        for(auto i : left)
            postorder.push_back(i);
        for(auto j : right)
            postorder.push_back(j);
        postorder.push_back(root->val);
        
        return postorder;*/
        /**
         *              1
         *             / \
         *            2   3
         *           / \   \
         *          3   1   4
         *           \     /
         *            1   2
         */
        //3、非递归方法
        stack<TreeNode *> Stack;
        vector<int> postorder;
        
        TreeNode *current = root, *lastVisited = NULL;
        while(current != NULL || !Stack.empty()){
            while(current != NULL){
                Stack.push(current);
                current = current->left;
            }
            
            current = Stack.top();
            if(current->right == NULL || current->right == lastVisited){
                Stack.pop();
                postorder.push_back(current->val);
                lastVisited = current;
                current = NULL;
            }else{
                current = current->right;
            }
        }
        return postorder;
        
    }
};
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/82024?site