814.二叉树剪枝

链接：814.二叉树剪枝
难度：Medium
标签：树、深度优先搜索、二叉树
简介：返回移除了所有不包含 1 的子树的原二叉树。

题解 1 - cpp

• 编辑时间：2022-07-21
• 执行用时：4ms
• 内存消耗：8.4MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
   public:
    TreeNode *pruneTree(TreeNode *root) {
        bool check = false;
        return _pruneTree(root, &check);
    }
    TreeNode *_pruneTree(TreeNode *root, bool *check) {
        if (root == nullptr) {
            *check = false;
            return root;
        }
        bool checkl = false, checkr = false;
        root->left = _pruneTree(root->left, &checkl);
        root->right = _pruneTree(root->right, &checkr);
        if (root->val || checkl || checkr) {
            *check = true;
            return root;
        } else {
            *check = false;
            return nullptr;
        }
    }
};

题解 2 - rust

• 编辑时间：2022-07-21
• 内存消耗：2MB
• 编程语言：rust
• 解法介绍：dfs。

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn prune_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut check = false;
        let mut root = root;
        Solution::_prune_tree(&mut root, &mut check);
        root
    }
    fn _prune_tree(root: &mut Option<Rc<RefCell<TreeNode>>>, check: &mut bool) {
        if root.is_none() {
            *check = false;
            return;
        }
        let mut check_l = false;
        let mut check_r = false;
        Solution::_prune_tree(&mut root.as_ref().unwrap().borrow_mut().left, &mut check_l);
        Solution::_prune_tree(&mut root.as_ref().unwrap().borrow_mut().right, &mut check_r);
        if root.as_ref().unwrap().borrow().val == 1 || check_l || check_r {
            *check = true;
        } else {
            *root = None;
        }
    }
}

题解 3 - javascript

• 编辑时间：2022-07-21
• 执行用时：60ms
• 内存消耗：42.7MB
• 编程语言：javascript
• 解法介绍：dfs。

var pruneTree = function (root) {
  return _pruneTree(root)[0];
};
function _pruneTree(root) {
  if (!root) return [null, false];
  const [left, checkl] = _pruneTree(root.left);
  const [right, checkr] = _pruneTree(root.right);
  root.left = left;
  root.right = right;
  if (checkl || checkr || root.val === 1) {
    return [root, true];
  } else {
    return [null, false];
  }
}

题解 4 - javascript

• 编辑时间：2022-07-21
• 执行用时：68ms
• 内存消耗：43.9MB
• 编程语言：javascript
• 解法介绍：dfs。

function pruneTree(root: TreeNode | null): TreeNode | null {
  return _pruneTree(root)[0];
}
function _pruneTree(root: TreeNode | null): [TreeNode | null, boolean] {
  if (!root) return [null, false];
  const [left, checkl] = _pruneTree(root.left);
  const [right, checkr] = _pruneTree(root.right);
  root.left = left;
  root.right = right;
  if (checkl || checkr || root.val === 1) {
    return [root, true];
  } else {
    return [null, false];
  }
}