统计和生成所有不同的二叉树

给定一个整数N，如果N<1，代表空树，否则代表中序遍历结果为{1, 2, 3… N}。请返回可能的二叉树结构有多少。

统计所有不同的二叉树

如果中序遍历有序且无重复值，则二叉树必为搜索二叉树。

采用动态规划计算。data[i]代表i个节点的搜索二叉树有多少种可能。又包括以1为头节点，以2为头节点，…，一直到以N为头节点。 以i为头节点时，等于左子树的种数，乘以右子树的种数。data[i] = data[i-1]* data[N-i]。

fn num_trees(n: i32) -> i32 {
    if n < 2 {
        return 1;
    }

    let mut data = vec![0; (n + 1) as usize];
    data[0] = 1;
    for i in 1..=n {
        for j in 1..=i {
            data[i as usize] += data[(j - 1) as usize] * data[(i - j) as usize];
        }
    }
    return data[n as usize];
}

进阶 生成所有不同的二叉树

N的含义不变，假设可能的二叉树有M种，请返回M个二叉树头节点，每个代表一种结构。

rust实现

#[derive(Clone)]
pub struct Node {
    pub val: i32,
    pub left: Option<Box<Node>>,
    pub right: Option<Box<Node>>,
}

impl Node {
    pub fn new(val: i32) -> Self {
        Node {
            val,
            left: None,
            right: None,
        }
    }
}

pub fn generate_trees(n: i32) -> Vec<Option<Box<Node>>> {
    generate(1, n)
}

fn generate(start: i32, end: i32) -> Vec<Option<Box<Node>>> {
    let mut res = Vec::new();
    if start > end {
        res.push(None);
        return res;
    }

    for i in start..=end {
        let head = Node::new(i);
        let left_trees = generate(start, i - 1);
        let right_trees = generate(i + 1, end);

        for left in &left_trees {
            for right in &right_trees {
                let mut new_head = head.clone();
                new_head.left = left.clone();
                new_head.right = right.clone();
                res.push(Some(Box::new(new_head)));
            }
        }
    }
    res
}

#[cfg(test)]
mod tests {

    use crate::{generate_trees, num_trees};

    #[test]
    fn it_works() {
        let res = num_trees(2);

        assert_eq!(res, 2);
    }

    #[test]
    fn it_works_2() {
        let num = 4;
        let res = generate_trees(num);
        assert_eq!(res.len(), num_trees(num) as usize);
    }
}

#### java版本


```java
public List<Node> generateTrees(int n) {
    return generate(1, n);
}

private List<Node> generate(int start, int end) {
    List<Node> res = new ArrayList<>();
    if (start > end) {
        res.add(null);
    }

    Node head = null;
    for (int i = start; i <= end; i++) {
        head = new Node(i);
        List<Node> left = generate(start, i - 1);
        List<Node> right = generate(i + 1, end);
        for (Node l : left) {
            for (Node r : right) {
                head.left = l;
                head.right = r;
                res.add(cloneTree(head));
            }
        }

    }
    return res;
}

public Node cloneTree(Node root) {
    if (root == null) return null;
    Node node = new Node(root.val);
    node.left = cloneTree(root.left);
    node.right = cloneTree(root.right);
    return node;
}

Box clone

在堆上重新分配一块区域，用不同的指针指向分配的新区域。因此，有两个保存一样数据，但是内存区域不同。

fn main() {
    let x = Box::new(5);
    let y = x.clone();

    // 获取指针地址
    let x_ptr = Box::into_raw(x); // 获取 x 的原始指针并消耗 Box
    let y_ptr = Box::into_raw(y); // 获取 y 的原始指针并消耗 Box

    // 使用 assert 判断地址是否相等
    assert!(!std::ptr::eq(x_ptr, y_ptr), "x 和 y 的地址应该不相等");

    // 打印指针地址
    println!("Address of x: {:p}", x_ptr);
    println!("Address of y: {:p}", y_ptr);
    println!("Address of z: {:p}", y_ptr);

    // 记得在使用完原始指针后释放内存
    unsafe {
        let _ = Box::from_raw(x_ptr);
        let _ = Box::from_raw(y_ptr);
    }

    // Address of x: 0x55e91ead3b80
    // Address of y: 0x55e91ead3ba0
}

评论