Java&C++题解与拓展——leetcode1022.从根到叶的二进制数之和【么的新知识】

• 题目要求
• 思路一：递归
• • Java
  • C++
  • Rust
• 思路二：迭代
• • Java
  • C++
  • Rust
• 总结

• 没什么好说的、DFS拼出来每个数，然后加起来。

class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return DFS(root, 0);
    }

    int DFS(TreeNode root, int pre) {
        int res = 0, cur = (pre << 1) + root.val;
        if(root.left != null)
            res += DFS(root.left, cur);
        if(root.right != null)
            res += DFS(root.right, cur);
        return root.left == null && root.right == null ? cur : res;
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        return DFS(root, 0);
    }

    int DFS(TreeNode* root, int pre) {
        int res = 0, cur = (pre << 1) + root->val;
        if(root->left != nullptr)
            res += DFS(root->left, cur);
        if(root->right != nullptr)
            res += DFS(root->right, cur);
        return root->left == nullptr && root->right == nullptr ? cur : res;
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn sum_root_to_leaf(root: Option>>) -> i32 {
        fn DFS(root: &Option>>, mut cur: i32) -> i32 {
            return if let Some(node) = root {
                cur = (cur << 1) | node.borrow().val;
                if node.borrow().left.is_none() && node.borrow().right.is_none() { cur }
                else { DFS(&node.borrow().left, cur) + DFS(&node.borrow().right, cur) }
            }
            else { 0 };
        }
        DFS(&root, 0)
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

• 遍历并修改当前节点值为已拼好部分。

class Solution {
    public int sumRootToLeaf(TreeNode root) {
        int res = 0;
        Deque que = new ArrayDeque<>();
        que.addLast(root);
        while(!que.isEmpty()) {
            TreeNode cur = que.pollFirst();
            if(cur.left != null) {
                cur.left.val = (cur.val << 1) + cur.left.val;
                que.addLast(cur.left);
            }
            if(cur.right != null) {
                cur.right.val = (cur.val << 1) + cur.right.val;
                que.addLast(cur.right);
            }
            if(cur.left == null && cur.right == null)
                res += cur.val;
        }
        return res;
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)

class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        int res = 0;
        queue que;
        que.push(root);
        while(!que.empty()) {
            TreeNode* cur = que.front();
            que.pop();
            if(cur->left != nullptr) {
                cur->left->val = (cur->val << 1) + cur->left->val;
                que.push(cur->left);
            }
            if(cur->right != nullptr) {
                cur->right->val = (cur->val << 1) + cur->right->val;
                que.push(cur->right);
            }
            if(cur->left == nullptr && cur->right == nullptr)
                res += cur->val;
        }
        return res;
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)

【有点复杂的、不太懂refcall所以没有按上面两种语言的思路写、不改原树而是维护一个 l e v lev lev和一个 t o t tot tot、但大差不差】

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn sum_root_to_leaf(root: Option>>) -> i32 {
        let mut res = 0;
        let mut tot = 0;
        let mut lev = -1;

        let mut que = vec![];

        if let None = root {
            return 0;
        }

        que.push((root.unwrap(), 0));

        while que.len() > 0 {
            let (cur, curLev) = que.pop().unwrap();
            let cur = cur.borrow();
            tot = tot >> (lev - curLev + 1);
            tot = (tot << 1) + cur.val;

            lev = curLev;

            if cur.left.is_some() {
                que.push((cur.left.clone().unwrap(), curLev + 1));
            }
            if cur.right.is_some() {
                que.push((cur.right.clone().unwrap(), curLev + 1));
            }

            if cur.left.is_none() && cur.right.is_none() {
                res += tot;
            }
        }

        res
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)

简单的DFS应用，只有Rust的迭代卡了一会。