< 返回版块

463642759 发表于 2018-12-19 11:48

Tags:rc, refcell, option

一道leetcode算法题

894. All Possible Full Binary Trees

已经用py AC

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def allPossibleFBT(self, N):
        """
        :type N: int
        :rtype: List[TreeNode]
        """
        if N == 1:
            return [TreeNode(0)]
        
        if N % 2 == 0:
            return []
        
        ans = []
        for i in range(1, N, 2):
            for l in self.allPossibleFBT(i):
                for r in self.allPossibleFBT(N - i - 1):
                    t = TreeNode(0)
                    t.left = l
                    t.right = r
                    ans.append(t)
                    
        return ans
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn all_possible_fbt(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        let mut arr = Vec::new();
        
        if n == 1 {
            arr.push(Some(Rc::new(RefCell::new(TreeNode::new(0)))));
            return arr;
        }
        
        if n % 2 == 0 {
            return arr;
        }
        
        for i in (1..n).step_by(2) {
            for left in Solution::all_possible_fbt(i) {
                for right in Solution::all_possible_fbt(n - i - 1) {
                    let mut t = TreeNode::new(0);
                    t.left = left.clone();
                    t.right = right.clone();
                    arr.push(Some(Rc::new(RefCell::new(t))));
                }
            }
        }
        
        arr
    }
}

同样的算法 结果却不对 是哪里写错了呢

t.left = left.clone(); t.right = right.clone(); 这两行有问题吗

评论区

写评论
Aloxaf 2018-12-21 11:08

你说的没错, 国际版交上去不对诶...... 而且同样的数据 Run Code 没问题, Submit 就WA, 估计是 LeetCode 的问题...

@463642759 AC了吗? 我py是AC rust是Wrong Answer 不是中国区

@Aloxaf 在中国区交了一下你的代码, 没啥问题...

作者 463642759 2018-12-21 10:28

AC了吗? 我py是AC rust是Wrong Answer 不是中国区

@Aloxaf 在中国区交了一下你的代码, 没啥问题...

Aloxaf 2018-12-20 19:40

在中国区交了一下你的代码, 没啥问题...

1 共 3 条评论, 1 页