代码随想录训练营Day11 | 226.翻转二叉树 - 101. 对称二叉树 - 104.二叉树的最大深度 - 111.二叉树的最小深度

226.翻转二叉树

• 题目链接：226.翻转二叉树
• 思路：遍历二叉树，遍历的时候交换左右节点即可
• 代码：

TreeNode* invertTree(TreeNode* root) {
        reverse(root);
        return root;
    }
    // 迭代法，层序遍历
	void f2(TreeNode* root) {
		 queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                swap(node->left, node->right); // 节点处理
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return root;
	}
	// 递归法
    void reverse(TreeNode* root) {
        if(!root)
            return;
            
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        reverse(l);
        reverse(r);
        root->left = r;
        root->right = l;
    }

101. 对称二叉树

• 题目链接：101. 对称二叉树
• 思路：遍历的时候，分别遍历比较左子树的右子树，和右子树的做子树，左子树的左子树和右子树的右子树对应即可
• 代码：

/**
 * 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) {}
 * };
 */
class Solution {
public:
	// 递归法
    bool isEqual(TreeNode* right, TreeNode* left) {
        if(!right || !left)
            return right == left;
        return right->val == left->val && isEqual(right->left, left->right) && isEqual(right->right, left->left);
    }

	// 迭代法
    bool isEqualIter(TreeNode* u, TreeNode* v) {
        queue <TreeNode*> q;
        q.push(u); q.push(v);
        while (!q.empty()) {
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if (!u && !v) continue;
            if ((!u || !v) || (u->val != v->val)) return false;

            q.push(u->left); 
            q.push(v->right);

            q.push(u->right); 
            q.push(v->left);
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
        if(!root)
            return true;
        return isEqualIter(root->left, root->right);
    }
};

104.二叉树的最大深度

• 题目链接：104.二叉树的最大深度
• 思路：遍历二叉树，记录最大深度即可
• 代码：

class Solution {
public:
	// 递归法
	int maxRecur(TreeNode* root) {
		if (root == nullptr) {
            return 0;
        }
        int l_depth = maxDepth(root->left);
        int r_depth = maxDepth(root->right);
        return max(l_depth, r_depth) + 1;
	}
	// 迭代法，层序遍历
	int maxIter(TreeNode* root) {
		if (root == nullptr) return 0;
	    queue<TreeNode*> Q;
	    Q.push(root);
	   int ans = 0;
	    while (!Q.empty()) {
           int sz = Q.size();
            while (sz > 0) {
                TreeNode* node = Q.front();Q.pop();
                if (node->left) Q.push(node->left);
                if (node->right) Q.push(node->right);
                sz -= 1;
            }
            ans += 1;
        } 
        return ans;
	}
    int maxDepth(TreeNode* root) {
        return maxRecur(root);
    }
};

111.二叉树的最小深度

• 题目链接：111.二叉树的最小深度
• 思路：遍历二叉树记录最小深度，相比最大深度，这里记录最小深度时，需要记录的是到叶子节点的最小深度，需要比最大深度多两个判断
• 代码：

class Solution {
public:
    // 递归法
	int minDepthRecur(TreeNode *root) {
		if (root == nullptr) {
            return 0;
        }
        if (root->right == nullptr) {
            return minDepthRecur(root->left) + 1; // 左子树的最小高度
        }
        if (root->left == nullptr) {
            return minDepthRecur(root->right) + 1; // 右子树的最小高度
        }
        return min(minDepthRecur(root->left), minDepthRecur(root->right)) + 1;
	}
	
	// 迭代法，层序遍历
	int minDepthIter(TreeNode *root) {
		if (root == nullptr) 
            return 0;
     
        queue<pair<TreeNode *, int> > que; // 记录节点和深度
        que.emplace(root, 1);
        while (!que.empty()) {
            TreeNode *node = que.front().first;
            int depth = que.front().second;
            que.pop();
            if (node->left == nullptr && node->right == nullptr) {
                return depth; // 没有子树，叶子节点，最先到达的叶子节点的高度为最小深度
            }
            if (node->left != nullptr) {
                que.emplace(node->left, depth + 1); // 左子树的深度
            }
            if (node->right != nullptr) { // 右子树的深度
                que.emplace(node->right, depth + 1);
            }
        }
        return 0;
	}

    int minDepth(TreeNode *root) {
		return minDepthRecur(root);
    }
};