Notice
Recent Posts
Recent Comments
Link
.Zzumbong
[leetCode/JS] 872. Leaf-Similar Trees ๋ณธ๋ฌธ
๋์ด๋ [ ๐ ] Easy
๋ฌธ์ ์ค๋ช
Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.
For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8)
.
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return true
if and only if the two given trees with head nodes root1
and root2
are leaf-similar.
2๊ฐ์ 2์ง ํธ๋ฆฌ๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํธ๋ฆฌ๋ง๋ค ๋ง์ง๋ง leaf ๊ฐ ์์์ ๊ฐ์ด ๊ฐ์ ๋ true๋ฅผ ๋๊ธด๋ค.
์ ์ถ๋ ฅ ์
Example 1:
Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true
Example 2:
Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false
Constraints
- The number of nodes in each tree will be in the range
[1, 200]
. - Both of the given trees will have values in the range
[0, 200]
.
๋ด ์๋ฃจ์
- ๋น์ฐํ ๊ธฐ๋ณธ์ ์ธ DFS ๋ฐฉ์์ผ๋ก ํ์ด์ผํ๋ค.
- left, right๊ฐ ์กด์ฌํ๋ฉด dfs()๋ฅผ ํธ์ถํ๊ณ ๋๋ค ๊ฐ์ด ์๋ ๋ง์ง๋ง Leaf ์ผ ๋, nodes์ `/${node.val}` ๋ก ์ ์ฅํ๋ค.
- /๊ฐ ํ์ํ ์ด์ ๋ 1,2,3 ๊ณผ 12,3์ด ๊ฐ์ ๊ฐ์ด ๋๊ธฐ ๋๋ฌธ.
var leafSimilar = function(root1, root2) {
const getLastNode = (root) => {
let nodes = '';
const dfs = (node) => {
if(node.left) dfs(node.left)
if(node.right) dfs(node.right)
if(!node.left && !node.right) nodes += `/${node.val}`
}
dfs(root);
return nodes;
}
return getLastNode(root1) === getLastNode(root2);
};
๊ฐ์ํ
- easy ๋ฌธ์ ์ผ ์๋ก ๋ต์ ํ๋๋ก ๊ท๊ฒฐ๋ ์ ๋ฐ์ ์๋๋ณด๋ค ๋ค๋ฅธ ์ฌ๋๋ค์ ์๋ฃจ์ ๋ ๋น์ทํ ๋ฐฉ์์ด๋ค.
- ๋ฉ๋ชจ๋ฆฌ๋ ์กฐ๊ธ ๋ง์ด ์ฌ์ฉํ๋ค. ์์ง! ๋ ์ ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฌ์ฉํ ์๋ฃจ์ ์ ๋ด๋ ๋ฌด๊ฑฐ์๋ณด์ด๋๋ฐ..
- ํ์ง๋ง ๋นจ๋์ฃ ?
'coding test > leetCode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[leetCode/JS] 1339. Maximum Product of Splitted Binary Tree (0) | 2022.12.10 |
---|---|
[leetCode/JS] 1026. Maximum Difference Between Node and Ancestor (0) | 2022.12.09 |
[leetCode/JS] 938. Range Sum of BST (0) | 2022.12.07 |
[leetCode/JS] 328. Odd Even Linked List (0) | 2022.12.06 |
[leetCode/JS] 876. Middle of the Linked List (0) | 2022.12.05 |
0 Comments