Question

Formatted question description: https://leetcode.ca/all/101.html

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

Constraints:

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

Follow up: Could you solve it both recursively and iteratively?

Algorithm

It is necessary to compare whether the value of the left child node of n1 and the value of the right child node of n2 are equal, and also whether the value of the right child node of n1 and the value of the left child node of n2 are equal.

Code

import java.util.Stack;

public class Symmetric_Tree {

	public static void main(String[] args) {

	}

	/**
	 * Definition for a binary tree node.
	 * public class TreeNode {
	 *     int val;
	 *     TreeNode left;
	 *     TreeNode right;
	 *     TreeNode(int x) { val = x; }
	 * }
	 */

	public class Solution_iteration {
	    public boolean isSymmetric(TreeNode root) {

	        if (root == null) {
	        	return true;
	        }


	        Stack<TreeNode> sk1 = new Stack<TreeNode>();
	        Stack<TreeNode> sk2 = new Stack<TreeNode>();

	        sk1.push(root.left);
	        sk2.push(root.right);

	        while (!sk1.isEmpty() && !sk2.isEmpty()) {
		        TreeNode r1 = sk1.pop();
		        TreeNode r2 = sk2.pop();

		        if (r1 == null && r2 == null) {
		        	continue;
		        } else if (r1 == null && r2 != null) {
		        	return false;
		        } else if (r1 != null && r2 == null) {
		        	return false;
		        } else if (r1.val != r2.val) {
		        	return false;
		        }

		        sk1.push(r1.left);
		        sk2.push(r2.right);

		        sk1.push(r1.right);
		        sk2.push(r2.left);
	        }

	        // @note: not necessary, since sk1 and sk2 are the same size, push/pop side by side
	        // if (!sk1.isEmpty() || !sk2.isEmpty()) {
	        // 	return false;
	        // }

	        return true;
	    }
	}

	public class Solution_recursion {
	    public boolean isSymmetric(TreeNode root) {

	        if (root == null) {
	        	return true;
	        }

	        return check(root.left, root.right);
	    }

	    private boolean check(TreeNode r1, TreeNode r2) {
	        if (r1 == null && r2 == null) {
	        	return true;
	        } else if (r1 == null && r2 != null) {
	        	return false;
	        } else if (r1 != null && r2 == null) {
	        	return false;
	        } else {
	        	return r1.val == r2.val
	        			&& check(r1.left, r2.right) && check(r1.right, r2.left);
	        }

	    }
	}

}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return dfs(root, root);
    }

    private boolean dfs(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null || root2 == null || root1.val != root2.val) {
            return false;
        }
        return dfs(root1.left, root2.right) && dfs(root1.right, root2.left);
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def dfs(root1, root2):
            if root1 is None and root2 is None:
                return True
            if root1 is None or root2 is None or root1.val != root2.val:
                return False
            return dfs(root1.left, root2.right) and dfs(root1.right, root2.left)

        return dfs(root, root)

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
  def isSymmetric(self, node):
    """
    :type root: TreeNode
    :rtype: bool
    """

    def helper(root, mirror):
      if not root and not mirror:
        return True
      if root and mirror and root.val == mirror.val:
        return helper(root.left, mirror.right) and helper(root.right, mirror.left)
      return False

    return helper(node, 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:
    bool isSymmetric(TreeNode* root) {
        function<bool(TreeNode*, TreeNode*)> dfs = [&](TreeNode* root1, TreeNode* root2) -> bool {
            if (!root1 && !root2) return true;
            if (!root1 || !root2 || root1->val != root2->val) return false;
            return dfs(root1->left, root2->right) && dfs(root1->right, root2->left);
        };
        return dfs(root, root);
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
	var dfs func(*TreeNode, *TreeNode) bool
	dfs = func(root1, root2 *TreeNode) bool {
		if root1 == nil && root2 == nil {
			return true
		}
		if root1 == nil || root2 == nil || root1.Val != root2.Val {
			return false
		}
		return dfs(root1.Left, root2.Right) && dfs(root1.Right, root2.Left)
	}
	return dfs(root, root)
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

const dfs = (root1: TreeNode | null, root2: TreeNode | null) => {
    if (root1 == root2) {
        return true;
    }
    if (root1 == null || root2 == null || root1.val != root2.val) {
        return false;
    }
    return dfs(root1.left, root2.right) && dfs(root1.right, root2.left);
};

function isSymmetric(root: TreeNode | null): boolean {
    return dfs(root.left, root.right);
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
    function dfs(root1, root2) {
        if (!root1 && !root2) return true;
        if (!root1 || !root2 || root1.val != root2.val) return false;
        return dfs(root1.left, root2.right) && dfs(root1.right, root2.left);
    }
    return dfs(root, root);
};

// 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 {
    fn dfs(root1: &Option<Rc<RefCell<TreeNode>>>, root2: &Option<Rc<RefCell<TreeNode>>>) -> bool {
        if root1.is_none() && root2.is_none() {
            return true;
        }
        if root1.is_none() || root2.is_none() {
            return false;
        }
        let node1 = root1.as_ref().unwrap().borrow();
        let node2 = root2.as_ref().unwrap().borrow();
        node1.val == node2.val
            && Self::dfs(&node1.left, &node2.right)
            && Self::dfs(&node1.right, &node2.left)
    }

    pub fn is_symmetric(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        let node = root.as_ref().unwrap().borrow();
        Self::dfs(&node.left, &node.right)
    }
}

101 - Symmetric Tree

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions