Welcome to Subscribe On Youtube
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) } }