filmov
tv
Test If A Binary Tree Is Symmetric ('Symmetric Tree' on Leetcode)
Показать описание
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Write a program to check if a binary tree is symmetric in structure as well as value.
A binary tree is symmetric if we can draw a vertical line down from the root and the left and right subtrees are mirrors of each other in structure and value.
The least this could be is O(n) time because we have to inspect all n nodes values to ensure that they conform to the tree being symmetric.
All we need to do is traverse the tree correctly with our recursion checking pairs for conformity.
The Conditions
If the root is null, the tree is symmetric.
Our checking function will take 2 nodes in to compare for symmetry.
Our Base Cases
If both nodes passed in are null, by default we have a symmetric tree.
If one node is null and the other is not, then we have incongruence, the tree is not symmetric since a pair failed.
If both nodes are null, then compare values. If values are equal, then good. Go left and go right.
How do we come up with this on the spot?
First recognize the base cases.
Then recognize we will need some way to compare pairs of nodes since that's what matters when checking for symmetry.
Even if this were an array that is how we would do it, pairs of indices.
Then recognize the way the recursive case must continue the work on the way down and your solution would look like this at the end.
Complexities
Time: O(n)
Space: O(h) (as we discussed, it can't really be O(n) worst case since
the first check would fail if the tree is skewed. The worst case IS O(h))
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++
This problem is problem 10.2 in the book Elements of Programming Interviews by Adnan Aziz
0:16:30
Check if a binary tree is binary search tree or not
0:07:57
Check Completeness of a Binary Tree - Leetcode 958 - Python
0:14:17
Test If A Binary Tree Is Height Balanced ('Balanced Binary Tree' on LeetCode)
0:04:20
How to solve (almost) any binary tree coding problem
0:13:11
Balanced Binary Tree - Leetcode 110 - Python
0:12:17
Test If A Binary Tree Is Symmetric ('Symmetric Tree' on Leetcode)
0:09:56
Validate Binary Search Tree - Depth First Search - Leetcode 98
0:15:42
Check if a binary tree is subtree of another tree | DS & Algo
0:10:29
Check if Binary Tree is Binary Search Tree
0:02:13
How to check if a binary tree is balanced in C#
0:04:47
Test if Balanced Binary Tree | Leetcode Question 110 Solution in Java
0:06:40
Symmetric Tree - Leetcode 101 - Python
0:04:05
Check if a binary tree is subtree of another binary tree | Part 1 | GeeksforGeeks
0:03:19
Check whether a binary tree is a full binary tree or not | Iterative Approach | GeeksforGeeks
0:06:57
Binary tree -35: Check if Two Binary Trees have same Structure
0:07:56
Binary Tree - 36: Check if Binary Tree is Foldable Tree
0:09:39
L46. Check if a tree is a BST or BT | Validate a BST
0:00:56
Balanced Binary Tree - Leetcode 110
0:09:21
Check if two binary trees are identical (Algorithm/code/program)
0:05:53
Check if removing an edge can divide a Binary Tree in two halves | GeeksforGeeks
0:16:58
Binary Tree - 71: Check if given Binary Tree is BST
0:07:15
Check if a tree is bst or not
0:07:40
check if a tree is subtree of another tree
0:08:05
Binary Tree - 86: Check if there exists a pair for given Sum in Binary Tree
Комментарии