(C++, Rust) - LeetCode (easy) 1013. Partition Array Into Three Parts With Equal Sum

https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/description/

LeetCode - The World's Leading Online Programming Learning Platform

자료구조 순회 문제였습니다.

📕 풀이방법

📔 풀이과정

트리를 직선형태로 순회하며 그 직선 형태의 길별로 값을 더하는 형태이므로 dfs형식으로 순회하는 것이 구현에 편리합니다.1. 왼쪽 subtree 결과 + 오른쪽 subtree 결과가 현재 node까지의 정답이 되는 재귀형태로 구현합니다. 따라서 다음 subtree를 재귀로 호출할 때 이전 값에서 누적해 정답을 구해줘야 합니다. 이전 값 * 2 + 현재 node의 값이 곧 이진수를 십진수로 변환한 값이 되므로 해당 값을 재귀함수 호출 시 인자로 넘겨주면서 호출해줍니다.3. 말단 node에 도착한 경우 해당 node의 val값을 구해 더한 값을 반환합니다.

 

* 말단 node가 아닌 기저 case(root==NULL)에서 정답을 반환하는 경우 말단 node level에서 같은 값이 두 번 더해지므로 정답이 아닙니다. 말단 node인 경우에만 바로 여태 누적되었던 값을 반환해줘야합니다.

---

📕 Code

📔 C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int dfs(TreeNode*root, int prev) {
        if(root == NULL) return 0;
        if(root -> left == NULL && root -> right == NULL) return prev*2+root->val; //말단 답 반환
        return dfs(root->right, prev*2+root->val) + dfs(root->left, prev*2+root->val);
    }
    int sumRootToLeaf(TreeNode* root) {
        return dfs(root,0);
    }
};

📔 Rust

// 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 sum_root_to_leaf(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        Self::dfs(root, 0)
    }

    fn dfs(root: Option<Rc<RefCell<TreeNode>>>, current: i32) -> i32 {
        if let Some(n) = root {
            let n = n.borrow();
            let new_val = current * 2 + n.val;

            if n.left.is_none() && n.right.is_none() {
                return new_val;
            }

            return Self::dfs(n.left.clone(), new_val) + Self::dfs(n.right.clone(), new_val);
        }
        0
    }
}

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.