把二叉搜索树转换为累加树

Category	Difficulty	Likes	Dislikes
algorithms	Medium (76.71%)	934	-

Tags

tree

Companies

amazon

给出二叉** 搜索 **树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键** 小于 **节点键的节点。
节点的右子树仅包含键** 大于** 节点键的节点。
左右子树也必须是二叉搜索树。
注意： 本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：

1
2
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

1
2
输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

1
2
输入：root = [1,0,2]
输出：[3,3,2]

示例 4：

1
2
输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

树中的节点数介于 0 和 104^ ^之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。

Discussion | Solution

解法

 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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// @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 {
    /// ## 解题思路
    /// - stack
    /// 1. 遍历二叉搜索树, 计算所有节点val的累积和sum;
    /// 2. 再一次中序二叉搜索树,
    pub fn convert_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        type TreeNodeOpt = Option<Rc<RefCell<TreeNode>>>;
        let mut tmp_nodes = Vec::new();
        let mut sum = 0; //节点值累积和
        let mut node = root.clone();
        // 中序遍历二叉树
        loop {
            // 将所有的左子节点入栈
            while let Some(n) = node {
                node = n.borrow_mut().left.clone();
                tmp_nodes.push(n);
            }
            // 弹出栈顶节点
            if let Some(n) = tmp_nodes.pop() {
                // 累加节点值
                sum += n.borrow().val;
                node = n.borrow_mut().right.clone();
            } else {
                // 没有待遍历节点
                break;
            }
        }

        let mut node = root.clone();
        // 中序遍历二叉树
        loop {
            // 将所有的左子节点入栈
            while let Some(n) = node {
                node = n.borrow().left.clone();
                tmp_nodes.push(n);
            }
            // 弹出栈顶节点
            if let Some(n) = tmp_nodes.pop() {
                // 处理当前节点
                let val = n.borrow().val;
                n.borrow_mut().val = sum;
                sum -= val;

                node = n.borrow().right.clone();
            } else {
                // 没有待遍历节点
                break;
            }
        }

        root
    }
}
// @lc code=end

把二叉搜索树转换为累加树

把二叉搜索树转换为累加树

解法

相关文章：