101. Symmetric Tree
Tags:
Easy
Skills:
Tree
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu kiểm tra một binary tree có phải là đối xứng qua root hay không. Tức là cây có phải là ảnh gương của chính nó không?
Ý tưởng chính
Approach - Recursive
Solution
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15function isSymmetric(root: TreeNode | null): boolean {
16 function isMirror(left: TreeNode | null, right: TreeNode | null): boolean {
17 if (!left && !right) return true;
18 if (!left || !right) return false;
19 if (left.val !== right.val) return false
20 return isMirror(left.left, right.right) && isMirror(left.right, right.left);
21 }
22
23 if (!root) return true;
24 return isMirror(root.left, root.right);
25};Approach (Iterative)
Solution
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15function isSymmetric(root: TreeNode | null): boolean {
16 if(!root) return true;
17 const stack: Array<[TreeNode| null, TreeNode | null]> = [[root.left, root.right]]
18 while(stack.length) {
19 const [a,b] = stack.pop();
20 if(!a && !b) continue;
21 if(!a || !b) return false;
22 if(a.val !== b.val) return false;
23 stack.push([a.left, b.right])
24 stack.push([a.right, b.left])
25 }
26 return true;
27};