代码随想录-二叉树

作者：weixin_40725706 | 2024-05-02 14:24:36

踩

代码随想录-二叉树

预备知识

docing

day14

144. 二叉树的前序遍历

    void lokup(TreeNode* root, vector<int>& result){
        if(root == nullptr) {return ;}
        result.push_back(root->val);
        lokup(root->left, result);
        lokup(root->right, result);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        // vector<int> ret;
        // lokup(root, ret);

        // return ret;

        // 非递归
        if(root == nullptr){return {};}
        std::stack<TreeNode*> q;
        vector<int> ret;
        TreeNode* current = root;
        while(!q.empty() || current!= nullptr){
            while(current != nullptr){
                q.push(current);
                ret.push_back(current->val);
                current = current->left;
            }

            current = q.top();
            q.pop();
            current = current->right;
        }
        return ret;
    }
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

94. 二叉树的中序遍历
 中序遍历与前序遍历不同的点在于push_back val的时机，前序遍历时第一次碰到的就是中节点，直接push_back。而中序遍历是在遍历完所有左节点之后,访问到的节点认为是目标值节点。
145. 二叉树的后序遍历
非迭代的普通写法中需要注意右节点重复的情况。

    vector<int> postorderTraversal(TreeNode* root) {
        if(root == nullptr) {return {};}

        std::stack<TreeNode*> q;
        TreeNode* current = root;
        vector<int>ret;
        TreeNode* pre = nullptr;
        while(!q.empty() || current!= nullptr){
            while(current != nullptr){
                q.push(current);
                current = current->left;
            }
            current = q.top();
            q.pop();
            // 当前为左节点; 无右节点或者右节点已经访问过了
            if(current->right == nullptr || current->right == pre){
                ret.push_back(current->val);
                pre = current;
                current = nullptr;
            }else{
                current = current->right;
            }
        }
        return ret;
    }
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

统一写法
统一了三种遍历的写法，使用了一个nullptr标记要访问的节点。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                st.push(node);                          // 中
                st.push(NULL);

                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左

            } else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        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
25
26

day15

102. 二叉树的层序遍历

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if(root == nullptr){return ret;}
        std::deque<TreeNode*> q;
        q.push_back(root);

        while(!q.empty()){
            // 记录当前层节点数
            size_t len = q.size();
            vector<int> res;
            for(int index = 0; index < len; ++index){
                auto* current = q.front();
                res.push_back(current->val);
                q.pop_front();
                if(current->left){
                    q.push_back(current->left);
                }
                if(current->right){
                    q.push_back(current->right);
                }
            }
            ret.emplace_back(res);
            
        }
        return ret;
    }
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

226. 翻转二叉树

    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) {return root;}
        // 先递归反转子树
        TreeNode* right = invertTree(root->right);
        TreeNode* left = invertTree(root->left);
        // 反转当前节点
        root->left = right;
        root->right = left;
        return root;
    }
1
2
3
4
5
6
7
8
9
10

101. 对称二叉树
递归的写法在于能够识别到两颗字数判断是：isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);

    bool isSymmetric(TreeNode* left, TreeNode* right){
        if(left == nullptr && right == nullptr){
            return true;
        }
        // 一个空一个非空，返回false
        if(left == nullptr ^ right == nullptr){
            return false;
        }
        // 值不相等
        if(right->val != left->val){
            return false;
        }
        return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
    }

    bool isSymmetric(TreeNode* root) {
        if(root == nullptr){return true;}
        return isSymmetric(root->left, root->right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

day16

104. 二叉树的最大深度

    int maxDepth(TreeNode* root) {
        if(root == nullptr){return 0;}

        return std::max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
1
2
3
4
5

111. 二叉树的最小深度
关键在于能理解有一个空子树一个非空子树时，此时取得是非空子树的深度，因为该节点肯定不是叶子节点，要计算该树的有效深度

    int minDepth(TreeNode* root) {
        if(root == nullptr){return 0;}
        if(root->left == nullptr && root->right == nullptr){return 1;}

        //  有一个为空子树
        if(root->left == nullptr ^ root->right == nullptr){
            // 空子树深度为0,实际是计算非空子树的深度
            return std::max(minDepth(root->left), minDepth(root->right)) + 1;
        }
        
        return std::min(minDepth(root->left), minDepth(root->right)) +1;
    }
1
2
3
4
5
6
7
8
9
10
11
12

222. 完全二叉树的节点个数

// 适用于任何二叉树
    int countNodes(TreeNode* root) {
        if(root == nullptr){return 0;}
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
1
2
3
4
5

题目说明了是满二叉树，除最后一层外每一层都是满的，最后一层的任意节点肯定是或存在左节点。

对于层高为h的满二叉树
- 节点数为 [2^(h-1), 2^h - 1]
- 节点k的左节点为 k << 1, 右节点 k >> 1 + 1
1
2
3

满二叉树

    int countNodes(TreeNode* root) {
        // if(root == nullptr){return 0;}
        // return countNodes(root->left) + countNodes(root->right) + 1;

        if(root == nullptr){return 0;}
        if(root->left == nullptr) {return 1;}
        TreeNode* current = root;
        int level = 0;
        while(current != nullptr){
            ++level;
            current = current->left;
        }
        int min_ele = 1 << (level - 1);
        int max_ele = (1 << level) - 1;

         while(min_ele <= max_ele){
             int mid = (max_ele + min_ele)>>1;
             if(HasNode(root, level, mid)){
                 min_ele = mid + 1;
             }else{
                 max_ele = mid - 1;
             }
         }
         
         // 跳出时的min_ele=mid+1, 只验证了mid存在其实不知道min_ele是否存在的
         return std::min(min_ele, max_ele);
    }

    bool HasNode(TreeNode* root, int level, int target){

        TreeNode* current = root;
        // 定位到最底层的上一层
        int bits = 1 << (level - 2);

        while(current != nullptr && bits > 0){
            if(target & bits){
                // 转向右子树
                current = current->right;
            }else{
                current = current->left;
            }

            // 向上移动一层
            bits = bits >> 1;
        }

        std::cout << "level:" << level << ",target:" << target << ",exist:" << (current!= nullptr) << std::endl;
        return current!= nullptr;
    }
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

day17

110. 平衡二叉树

    int GetHeight(TreeNode* root){
        if(root == nullptr){return 0;}
        return std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
    } 
    bool isBalanced(TreeNode* root) {
        if(root == nullptr){
            return true;
        }
        // 左右子树高度差小于1 && 左右子树都是平衡树
        return std::abs(GetHeight(root->left) - GetHeight(root->right)) <=1 && isBalanced(root->left) && isBalanced(root->right);
    }
1
2
3
4
5
6
7
8
9
10
11

257. 二叉树的所有路径

class Solution {
public:
    std::string combine(const std::vector<int>& vec){
        if(vec.empty()){return "";}
        std::string ret = std::to_string(vec[0]);
        for(int index = 1; index < vec.size(); ++index){
            ret.append("->").append(std::to_string(vec[index]));
        }
        return ret;
    }

    void LookUp(TreeNode* root, std::vector<int>& path){
        if(root == nullptr){
            return;
        }
        path.push_back(root->val);
        // 遍历到了根节点
        if(root->left == nullptr && root->right == nullptr){
            ret.push_back(combine(path));
            return;
        }
        
        if(root->left){
            LookUp(root->left, path);
            path.pop_back();	// 回溯
        }
        if(root->right){
            LookUp(root->right, path);
            path.pop_back();
        }
    }


    vector<string> binaryTreePaths(TreeNode* root) {
        std::vector<int> path;
        LookUp(root, path);
        return ret;
    }

    vector<string> ret;
};
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

404. 左叶子之和

关键在于搞清楚什么是左叶子 1. 叶子(左右节点都是空) 2. 该节点为父节点的左子节点

    int sumOfLeftLeaves(TreeNode* root) {
        if(root == nullptr){return 0;}

        std::queue<TreeNode*> q;
        q.push(root);

        int ret = 0;
        while(!q.empty()){
            TreeNode* current = q.front();
            q.pop();

            // 当前节点存在左节点
            if(current->left){
                // 左叶子
                if(current->left->left == nullptr && current->left->right == nullptr){
                    ret += current->left->val;
                }else{
                    q.push(current->left);
                }
            }
            // 当前节点存在右节点，该右节点肯定不是左叶子
            if(current->right && (current->right->left != nullptr || current->right->right != nullptr)){
                q.push(current->right);
            }
        }

        return ret;
    }
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

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