ch7-of-programmercarl-1

C++ C 代码随想录 二叉树 DFS BFS
刷题
发布日期:   2022-04-18

1 树的遍历

  移步至Coding Tips查看C语言-3.各种数据结构-3.3 树章节查看，包括树的建立以及四种遍历的实现方法，包括迭代遍历与递归遍历的实现，其中迭代遍历分为一般遍历和统一遍历两种，后者将前序遍历、中序遍历、后序遍历的代码进行了统一，仅需调整结点插入栈的顺序即可。

2 翻转二叉树

2.1 题目描述

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例1:

输入: root = [4,2,7,1,3,6,9]
输出: [4,7,2,9,6,3,1]

示例2:

输入: root = [2,1,3]
输出: [2,3,2]

示例3:

输入: root = []
输出: []

2.2 思路

  最简单的思路，直接递归，由于翻转二叉树相当于交换两个数。交换两个数我们需要先保存其中一个数，然后先交换其中一个，再交换另一个。翻转二叉树同样需要先保存其中一个结点，否则直接更改某个结点的左孩子指向，那么就无法再访问其原来的左孩子结点。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return nullptr;

        TreeNode *left = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(left);

        return root;
    }
};
  • C 实现
struct TreeNode* invertTree(struct TreeNode* root){
    if(!root) return NULL;

    TreeNode *left = root->left;
    root->left = invertTree(root->right);
    root->right = invertTree(left);

    return root;
}

3 对称二叉树

3.1 题目描述

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例1:

输入: root = [1,2,2,3,4,4,3]
输出: true

示例2:

输入: root = [1,2,2,null,3,null,3]
输出: false

3.2 思路

  • 递归：没啥好写的。递归函数中，如果左右结点均为NULL则为true，如果其中一个结点为NULL或两个结点值不等则为false, 否则进入下一层判断。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    bool check(TreeNode* left, TreeNode* right){
        if(!left && !right) return true;
        else if(!left || !right || left->val != right->val) return false;

        return check(left->left, right->right) && check(left->right, right->left);
    }

    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return check(root->left, root->right);
    }
}
  • C 实现 
bool judge(struct TreeNode* root1, struct TreeNode *root2){
    if(!root1 && !root2) return true;
    if((!root1||!root2)||root1->val!=root2->val){
        return false;
    }
    return judge(root1->left, root2->right) && judge(root1->right, root2->left);
}

bool isSymmetric(struct TreeNode* root){
    return judge(root, root);
}
  • 双向队列：队列头加右子树，队列尾加左子树，循环对队头和队尾的结点值进行判断。其中，如果左右结点仅有一个为NULL或左右节点的值不等则直接返回false，反则将左右节点的左右孩子都加入到队列中，依然还是左边在队尾、右边在队头，而且左边应该先把左孩子插入然后插右孩子，而右边先右孩子后左孩子(或者左先右后左，右则先左后右). 这种思路其实是DFS. ps: 双向队列的作用感觉有点像栈。
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root || (!root->left && !root->right)){
            return true;
        }else if(!root->left || !root->right){
            return false;
        }
        deque<TreeNode*> deq;
        deq.push_back(root->left);
        deq.push_front(root->right);
        while(!deq.empty()){
            TreeNode *left = deq.back(), *right = deq.front();
            deq.pop_back(), deq.pop_front();
            if(!left && !right){
                continue;
            }else if(!left || !right || (left->val != right->val)){
                return false;
            }
            deq.push_back(left->left);
            deq.push_back(left->right);
            deq.push_front(right->right);
            deq.push_front(right->left);
        }
        return true;
    }
};

  • 单向队列：类似双向队列，也是要注意插入顺序即可。先左左后右右再左右最后右左(或先左右后右左再左左最后右右)以保证队列中相邻位置为对称位置结点对。

  • Cpp 实现

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root || (!root->left && !root->right)){
            return true;
        }else if(!root->left || !root->right){
            return false;
        }
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while(!q.empty()){
            TreeNode *left = q.front();
            q.pop();
            TreeNode *right = q.front();
            q.pop();
            if(!left && !right){
                continue;
            }else if(!left || !right || left->val != right->val){
                return false;
            }
            q.push(left->left);
            q.push(right->right);
            q.push(left->right);
            q.push(right->left);
        }
        return true;
    }
};
  • C 实现
bool isSymmetric(struct TreeNode* root){
    if(root == NULL) return true;

    struct TreeNode *tmp[1000];
    int front = 0, rear = 0;
    struct TreeNode *left, *right;
    tmp[rear++] = root->left;
    tmp[rear++] = root->right;
    while(front != rear){ //队列不为空
        left = tmp[front++];
        right = tmp[front++];   
        if(!left && !right) 
            continue;
        if(!left || !right || left->val != right->val)
            return false;
        tmp[rear++] = left->left; 
        tmp[rear++] = right->right;
        tmp[rear++] = left->right;
        tmp[rear++] = right->left;   
    }
    return true;
}

4 二叉树的最大深度

4.1 题目描述

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7]，

   3
  / \\
 9 20
  /  \\
15 7

返回它的最大深度 3 。

4.2 思路

  • DFS: 递归.

  • BFS: 层序遍历，深度即为层数.

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int bfs(TreeNode* root){
        queue<TreeNode*> q;
        q.push(root);
        int cnt = 0;
        while(!q.empty()){
            ++cnt;
            int size = q.size();
            while(size--){
                TreeNode* cur = q.front();
                q.pop();
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
        }
        return cnt;
    }

    int maxDepth(TreeNode* root) {
        if(!root) return 0;

        //dfs
        //return max(maxDepth(root->left),maxDepth(root->right)) + 1;
        //bfs
        return bfs(root);
    }
};
  • C 实现
int bfs(struct TreeNode* root){
    int ans = 0;
    if(root == NULL) return ans;

    struct TreeNode* queue[1001];
    struct TreeNode* cur;
    int front = 0, rear = 0;
    queue[rear++] = root;
    while(front != rear){
        int last = rear;
        while(front != last){
            cur = queue[front++];
            if(cur->left != NULL) queue[rear++] = cur->left;
            if(cur->right != NULL) queue[rear++] = cur->right;
        }
        ans++;
    }
    return ans;
}

int maxDepth(struct TreeNode* root){
    if(root == NULL) return 0;
    //dfs
    return fmax(maxDepth(root->left), maxDepth(root->right)) + 1; 
    //bfs
    //return bfs(root);
}

5 二叉树的最小深度

5.1 题目描述

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例1:

输入: root = [3,9,20,null,null,15,7]
输出: 2

示例2:

输入: root = [2,null,3,null,4,null,5,null,6]
输出: 5

5.2 思路

  • BFS：当有一层遍历到NULL就返回即可。

  • DFS: 递归，求树的最小深度可以转换为左右子树的深度的最小值。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int bfs(TreeNode* root){
        queue<TreeNode*> q;
        q.push(root);
        int cnt = 0;
        while(!q.empty()){
            ++cnt;
            int size = q.size();
            while(size--){
                TreeNode* cur = q.front();
                q.pop();
                if(!cur->left && !cur->right) return cnt;
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
        }
        return cnt;
    }
    int minDepth(TreeNode* root) {
        //dfs
        if(!root) return 0;
        
        int mindepth = INT_MAX;
        if(root->left){
            mindepth = min(mindepth, minDepth(root->left));
        }
        if(root->right){
            mindepth = min(mindepth, minDepth(root->right));
        }
        return mindepth == INT_MAX ? 1: mindepth + 1;
        //bfs
        /*if(!root) return 0;
        return bfs(root);*/
    }
};
  • C 实现
int minDepth(struct TreeNode* root){
    int ans = 0;
    if(root == NULL) return ans;

    struct TreeNode *queue[100000], *cur;
    int front = 0, rear = 0;
    queue[rear++] = root;
    ans++;
    while(front != rear){
        int last = rear;
        while(front != last){
            cur = queue[front++];
            if(cur->left == NULL && cur->right == NULL) return ans;
            if(cur->left != NULL)  queue[rear++] = cur->left;
            if(cur->right != NULL) queue[rear++] = cur->right;
        }
        ans++;
    }
    return ans;
}

6 完全二叉树的节点个数

6.1 题目描述

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 $1 - 2^h$ 个节点。

示例1:

输入: root = [1,2,3,4,5,6]
输出: 6

示例2:

输入: root = []
输出: 0

示例3:

输入: [1]
输出: 1

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

6.2 思路

  • 最简单的就是直接遍历整棵二叉树。
  • 第二种思路是二分查找。先找到二叉树的最大高度，即通过一直访问左孩子结点直至左结点为NULL时计数器即为树的高度。由于是完全二叉树，找到树的高度后，树的结点数就在$2^k$到$2^{(k+1)}-1$之间,因而可以在这个范围进行查找。应当注意到，完全二叉树中结点的编号可以反映结点的位置，将编号转为二进制，除去最高位的1，其他二进制位为0则向左走、为1则向右走。
  • 递归，将树的节点数转换为求左子树的结点数、右子树的结点数以及根节点的加和。

完整代码如下：

  • 二分查找Cpp实现
class Solution {
public:
    int getHeight(TreeNode* root){
        TreeNode* cur = root;
        int res = 0;
        while(cur->left){
            cur = cur->left;
            ++res;
        }
        return res;
    }

    bool isExist(TreeNode* root, int num, int height){
        int b = 1 << (height-1);
        TreeNode* cur = root;
        while(cur && b > 0){
            if(!(b & num)){
                cur = cur->left;
            }else{
                cur = cur->right;
            }
            b >>= 1;
        }
        return cur != nullptr;
    }

    int countNodes(TreeNode* root) {
        if(!root) return 0;
        int height = getHeight(root);   
        int l = 1 << height, r = (1 << (height+1))-1;
        while(l < r){
            int m = l + (r - l + 1)/2;
            if(isExist(root, m, height)){
                l = m;
            }else{
                r = m - 1;
            }
        }
        return l;
    }
};
  • 递归Cpp实现
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root) return 0;

        int lHeight = 0, rHeight = 0;
        TreeNode* cur = root;
        while(cur->left){
            cur = cur->left;
            ++lHeight;
        }

        while(cur->right){
            cur = cur->right;
            ++rHeight;
        }
        if(lHeight == rHeight){
            return (1<<(lHeight+1))-1;
        }
        return countNodes(root->left)+countNodes(root->right) + 1;
    }
};

7 平衡二叉树

7.1 题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

  一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例1:

输入: root = [3,9,20,null,null,15,7]
输出: true

示例2:

输入: root = [1,2,2,3,3,null,null,4,4]
输出: false

示例3:

输入: []
输出: true

7.2 思路

  • 自底而上: 计算树的深度即可。

  • 自顶而下: 遍历树来求左右子树的高度(最底下高度为0)，如果当前结点为NULL则说明当前遍历的子树高度为0; 自下而上计算子树的高度，当左右高度差超过1时将子树高度置为-1(其他负数均可，或者用一个全局bool变量来作为标识)，主函数中检测到返回值为-1则说明不是高度平衡的二叉树，返回false，否则返回true.

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int getDepth(TreeNode* root){
        if(!root){
            return 0;
        }
        return max(getDepth(root->left), getDepth(root->right))+1;
    }

    int getHeight(TreeNode* root){
        if(!root) return 0;

        int lHeight = getHeight(root->left);
        if(lHeight == -1) return -1;
        int rHeight = getHeight(root->right);
        if(rHeight == -1) return -1;
        return abs(lHeight - rHeight) > 1 ? -1 : max(lHeight, rHeight) + 1;
    }

    bool isBalanced(TreeNode* root) {
        //自顶而下求深度
        /*if(!root) return true;
        int l = getDepth(root->left), r = getDepth(root->right);
        return (abs(l - r)<=1)&&isBalanced(root->left)&&isBalanced(root->right);*/
        //自底而上求高度
        return getHeight(root) != -1;
    }
};
  • C 实现
int getHeight(struct TreeNode *root){
    if(root == NULL) return 0;

    int leftHeight = getHeight(root->left);
    if(leftHeight == -1) return -1;
    int rightHeight = getHeight(root->right);
    if(rightHeight == -1) return -1;
    return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + fmax(leftHeight, rightHeight); 
}

bool isBalanced(struct TreeNode* root){
    return (getHeight(root) != -1);
}

8 二叉树的所有路径

8.1 题目描述

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例1:

输入: root = [1,2,3,null,5]
输出: [“1->2->5”,”1->3”]

示例2:

输入: root = [1]
输出: [“1”]

8.2 思路

  • DFS: 采用回溯算法，当遇到某个结点既没有左孩子也没有右孩子的时候就把暂存的路径插入到答案中，否则则将当前结点值插入暂存路径中并进行一下层结点的遍历。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    vector<string> res;
    void dfs(TreeNode* root, string path){
        if(!root->left && !root->right){
            path += to_string(root->val);
            res.emplace_back(path);
            return;
        }else{
            path += to_string(root->val);
            if(root->left) dfs(root->left, path + "->");
            if(root->right) dfs(root->right, path + "->");
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        if(!root) return res;

        string path = "";
        dfs(root, path);
        return res;
    }
};
  • C 实现
//int cnt = 0;
void traversal(struct TreeNode* root, int *tmpPath, char **path, int* returnSize, int cnt){
//void traversal(struct TreeNode* root, int *tmpPath, char **path, int* returnSize){
    struct TreeNode *cur = root;
    tmpPath[cnt++] = cur->val;
    if(cur->left == NULL && cur->right == NULL){
        int len = 0;
        for(int i = 0; i < cnt - 1; i++){
            len += sprintf(path[*returnSize]+len,"%d->",tmpPath[i]);
        }
        sprintf(path[*returnSize]+len,"%d",tmpPath[cnt-1]);
        (*returnSize)++;
        return;
    }
    if(cur->left){
        traversal(cur->left, tmpPath, path, returnSize, cnt);
        //traversal(cur->left, tmpPath, path, returnSize);
        //cnt--;    //cnt是局部变量，递归过程不修改，不用-1
    }               //-1是为了把叶子点去掉，如果是全局变量就要减去1
    if(cur->right){
        traversal(cur->right, tmpPath, path, returnSize, cnt);
        //traversal(cur->right, tmpPath, path, returnSize);
        //cnt--;
    }
    return;
}

char ** binaryTreePaths(struct TreeNode* root, int* returnSize){
    int cnt = 0;
    char **ret = (char **)malloc(sizeof(char *)*100);
    for(int i = 0; i<100; i++){
        ret[i] = malloc(sizeof(char)*1000);
    }
    int *path = (int *)malloc(sizeof(int)*100);
    *returnSize = 0;
    if(root == NULL) return ret;
    traversal(root, path, ret, returnSize, cnt);
    //traversal(root, path, ret, returnSize);
    return ret;
}

9 左叶子之和

9.1 题目描述

给定二叉树的根节点 root ，返回所有左叶子之和。

示例1:

输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例2:

输入: root = [1]
输出: 0

9.2 思路

  就是找到某个结点的左节点，其左右节点均为NULL时就把该节点的值加到答案中。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int bfs(TreeNode* root){
        queue<TreeNode*> q;
        q.push(root);
        int res = 0;
        while(!q.empty()){
            TreeNode* cur = q.front();
            q.pop();
            if(cur->left && !cur->left->left && !cur->left->right){
                res += cur->left->val;
            }
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
        return res;
    }
    int sumOfLeftLeaves(TreeNode* root) {
        if(!root){
            return 0;
        }
        return bfs(root);
    }
};
  • C 实现
int sumOfLeftLeaves(struct TreeNode* root){
    int ans = 0;
    if(root == NULL) return ans;

    struct TreeNode *stack[1000], *cur = root;
    int stack_top = 0;
    while(cur != NULL || stack_top != 0){
        while(cur != NULL){
            stack[stack_top++] = cur;
            cur = cur->left;
            if(cur && !cur->left && !cur->right){
                ans += cur->val;
            }
        }
        cur = stack[--stack_top];
        cur = cur->right;
    }
    return ans;
}

10 找树左下角的值

10.1 题目描述

给定一个二叉树的 根节点 `root``，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例1:

输入: root = [2,1,3]
输出: 1

示例2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

10.2 思路

  • BFS: 层序遍历，直至最后一层，返回队列的队头即可。

完整代码如下：

  • Cpp实现
class Solution {
public:
    int bfs(TreeNode* root){
        queue<TreeNode*> q;
        q.push(root);
        int res = 0;
        while(!q.empty()){
            int size = q.size();
            for(int i = 0; i < size; ++i){
                TreeNode* cur = q.front();
                q.pop();
                if(i == 0){
                    res = cur->val;
                }
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
        }
        return res;
    }

    int findBottomLeftValue(TreeNode* root) {
        if(!root) return 0;
        return bfs(root);
    }
};
  • C实现
int findBottomLeftValue(struct TreeNode* root){
    if(root == NULL) return -1;
    else if(!root->left && !root->right) return root->val;

    struct TreeNode *queue[10001];
    int front = 0, rear = 0;
    queue[rear++] = root;
    int last, prev;
    while(front != rear){
        last = rear, prev = front;
        while(front != last){
            struct TreeNode *cur = queue[front++];
            if(cur->left) queue[rear++] = cur->left;
            if(cur->right) queue[rear++] = cur->right;
        }
    }
    return queue[prev]->val;
}

总结

文章作者: Vyron Su
文章链接: http://example.com/2022/04/18/ch7-of-programmercarl-1/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Vyron Su !
C++ C 代码随想录 二叉树 DFS BFS