226. Invert Binary Tree

Description of the Problem

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: []

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Solution

Tags: Rust Binary Tree

Explanation

Recursively invert left and right sub-trees. And swap left and right sub-trees.

Code(C++)

/**
 * 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 == nullptr) 
            return nullptr;
        TreeNode * tempNode = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(tempNode);
        return root;
    }
};

Code (Rust)

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
       return root.map( 
            |root| {
                {
                    let mut node = root.borrow_mut();
                    let left = node.left.clone();
                    let right = node.right.clone();
                    node.right = Self::invert_tree(left);
                    node.left = Self::invert_tree(right);
                }
                return root;
            } 
       );
    }
}

Complexity

\(h\) is the height of the tree
\(n\) is the number of nodes in the tree

Time complexity:

\( T(n) = O(n) \)
- Traverse all nodes in the tree.

Auxiliary Space:

\( S(h) = O(h) \)
- the depth of the tree is the depth of recursive tree.

Reference

Rust Solution Provided by nitrey

Leetbook