How to iter this tree struct

help
1

Say I have a complete binary tree, and I want to get its height or depth. Here's my code:

 #[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;


    fn get_depth(r: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if r.is_none() {
            return 0;
        }
        1 + Self::get_depth(&r.as_ref().unwrap().borrow().left)
    }

And then I want to use non-recursive code to solve this problem, but it cannot compile. How should I fix it:

    fn get_depth(r: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut cur = r;
        let mut count = 0;
        while cur.is_some() {
            count+=1;
            cur = &cur.as_ref().unwrap().borrow().left; // err: borrow creates a temporary var...
        }
        count
    }
2

Option<Rc<RefCell<TreeNode>>> seems like a code smell without further context. Is there some particular reason to not use Option<Box<TreeNode>>?

3

It's a problem from leetcode, and I have to finish the function based on the func template. The struct define is part of the template

4

It's not possible to do iteratively because accessing the contents of the RefCell requires a guard with drop code, so accessing something 10 nodes deep will mean having ten guards with destructors active while moving down the tree.

It may be possible with a mutable reference, because the uniqueness guarantee allows you to skip the requirement of a drop guard.

5

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.