Leetcode Study Day 33

Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

Example 1:


Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2:


Input: root = [2,1,3]
Output: [2,3,1]
Example 3:

Input: root = []
Output: []

Solution

I got the post order treversal idea from here

In his explanation, we first go to the most left node, when we reach the most left node, we go back to its parent node, then go to the right node of the parent node, if it is also the bottom node, we swap this two nodes. We repeat this process until we reach the root node.

/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if (!root)
            return nullptr;
        invertTree(root->left);
        invertTree(root->right);
        TreeNode * temp = root->left;
        root -> left = root -> right;
        root -> right = temp;
        return root;
    }
};

Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:


Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:


Input: root = [1,2,2,null,3,null,3]
Output: false

My solution

I create a function to check whether the passed nodes are the same, if so, we pass its children into this function again. If not, we return false. We call this function in the main function.

/**
 * 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 isSymNode(TreeNode* leftN, TreeNode* rightN){
        if (!leftN && !rightN)
            return true;
        else if (!leftN && rightN || leftN && !rightN)
            return false;
        else if (leftN->val != rightN->val)
            return false;
        else{
            return(isSymNode(leftN->left, rightN->right) && isSymNode(leftN->right, rightN->left));
        }
    }
    bool isSymmetric(TreeNode* root) {
        return(isSymNode(root->left,root->right));
    }
};