1
2
3
4
5

    1
   / \
  2   5
 / \   \
3   4   6

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

// @lc code=start
// 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::cell::RefCell;
use std::rc::Rc;
impl Solution {
    /// ## 解题思路
    pub fn flatten(root: &mut Option<Rc<RefCell<TreeNode>>>) {
        match root {
            None => {}
            Some(node) => {
                // 取下当前节点左子树
                let mut left = node.borrow_mut().left.take();
                // 将左子树展开为链表
                Solution::flatten(&mut left);

                // 取下当前节点右子树
                let mut right = node.borrow_mut().right.take();
                // 将右子树展开为链表
                Solution::flatten(&mut right);

                // 将左子树展开后链表表头接到当前节点右指针后
                node.borrow_mut().right = left;

                // 遍历已接左子树链表, 找到最后一个节点
                let mut p = node.clone();
                while p.borrow().right.is_some() {
                    let tmp = p.borrow().right.clone().unwrap();
                    p = tmp;
                }
                // 将右子树链表头接到最后一个节点右子树上
                p.borrow_mut().right = right;
            }
        }
    }
}
// @lc code=end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/*
## 解题思路
   * 递归
   1. 先分别展开左右子树；
   2. 将root->right指向左子树link头；
   3. 设置一个遍历指针，移动到左子link末尾；
   4. 末尾节点right指针指向右子link；
*/
class Solution {
public:
    void flatten(TreeNode* root) {
        if(!root){
            return;
        }
        flatten(root->left);
        flatten(root->right);
        if(root->left) {
            auto right = root->right;
            root->right = root->left;
            root->left = NULL;
            auto p = root->right;
            while(root->right) {
                root = root->right;
            }
            root->right = right;
        }
    }
};