Re: [閒聊] 每日LeetCode
872. Leaf-Similar Trees
https://leetcode.com/problems/leaf-similar-trees/description/
給定兩棵二元樹 root1 與 root2 ,
從左到右來看,
傳回這兩棵樹的葉節點是否相似。
--
思路:
葉節點的定義是左右都沒有子節點,
所以只要發現葉節點時,
就把該節點的值傳到記錄葉節點的陣列中。
因為葉節點要從左到右去找,
在遞迴的時候等左邊的節點都搜完之後才會跑右邊的
--
Python3 code:
class Solution:
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]
) -> bool:
leaf1, leaf2 = [], []
def dfs(node, leaf):
if node is None: return
if node.left is None and node.right is None: leaf.append(node.val)
dfs(node.left, leaf)
dfs(node.right, leaf)
dfs(root1, leaf1)
dfs(root2, leaf2)
return leaf1 == leaf2
--
C++ Code:
class Solution {
private:
void dfs(TreeNode* node, vector<int> &leaf){
if (!node) return;
if (!node->left && !node->right) leaf.push_back(node->val);
dfs(node->left, leaf);
dfs(node->right, leaf);
}
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector<int> leaf1, leaf2;
dfs(root1, leaf1);
dfs(root2, leaf2);
return leaf1 == leaf2;
}
};
--
心得:
我測試了才發現 Python 的函數也可以傳址
--
咖啡是一種豆漿,
茶是一種蔬菜湯。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.84.252 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1704791581.A.619.html
→
01/10 01:40,
4月前
, 1F
01/10 01:40, 1F
討論串 (同標題文章)
完整討論串 (本文為第 596 之 719 篇):
閒聊
1
3