こんにちは、 @kz_morita です。 LeetCode で遊んでいて Rust で木構造の実装をしたのでまとめておきます． ちなみに，ソースコードこちらに雑に上げてます． https://github.com/foresta/rust-tree データ構造 以下のようなデータ構造で木構造を表現します． #[derive(Clone, Debug, PartialEq, Eq)]pubstruct TreeNode{pubval: String,publeft: Option<Rc<RefCell<TreeNode>>>,pubright: Option<Rc<RefCell<TreeNode>>>,}よくある木構造だと enum で表現して Box を使うものをよく見ると思いますが LeetCode で前提となっていた Rc<RefCell<TreeNode>> 形式で今回は考えます． 木構造自体は以下のようなものを作ります． fn create_tree_node()-> Rc<RefCell<TreeNode>>{// // A // B C // D E F // G H I J K // letmuta=TreeNode::new("A");letmutb=TreeNode::new("B");letmutc=TreeNode::new("C");letmutd=TreeNode::new("D");letmute=TreeNode::new("E");letmutf=TreeNode::new("F");letg=TreeNode::new("G");leth=TreeNode::new("H");leti=TreeNode::new("I");letj=TreeNode::new("J");letk=TreeNode::new("K");d.left=Some(Rc::new(RefCell::new(g)));d.right=Some(Rc::new(RefCell::new(h)));e.right=Some(Rc::new(RefCell::new(i)));f.left=Some(Rc::new(RefCell::new(j)));f.right=Some(Rc::new(RefCell::new(k)));b.left=Some(Rc::new(RefCell::new(d)));b.right=Some(Rc::new(RefCell::new(e)));c.right=Some(Rc::new(RefCell::new(f)));a.left=Some(Rc::new(RefCell::new(b)));a.right=Some(Rc::new(RefCell::new(c)));Rc::new(RefCell::new(a))}DFS 深さ優先探索するので，以下の順番で走査します． A → B → D → G → H → E → I → C → F → J → K