这道题需要注意的是，原本不是叶子节点的node,在删除操作之后也不能是叶子节点

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def sufficientSubset(self, root, limit):
        """
        :type root: TreeNode
        :type limit: int
        :rtype: TreeNode
        """
        leaf_node_id_dict = {}

        # calc sum , 利用先序遍历所有的节点
        stack = []
        pNode = root
        while len(stack) or pNode:
            if pNode:
                if pNode.left:
                    pNode.left.val += pNode.val
                if pNode.right:
                    pNode.right.val += pNode.val
                if pNode.left is None and pNode.right is None:
                    leaf_node_id_dict[id(pNode)] = 1
                stack.append(pNode)
                pNode = pNode.left
            else:
                pNode = stack.pop().right
        # self.show(root)

        #剪枝 从下往上遍历，如果叶子节点不满足条件，就剪掉叶子节点，
        #从下往上依次减掉, 所以用后序遍历，因为要用根节点取判断左右节点的叶子
        stack = []
        pNode, prev = root, None
        while len(stack) or pNode:
            # print(len(stack))
            if pNode:
                stack.append(pNode)
                pNode = pNode.left
            else:
                pNode = stack[-1]
                if pNode.right == None or pNode.right == prev:
                    if pNode.left and pNode.left.left == None and pNode.left.right == None and pNode.left.val < limit:
                        pNode.left = None
                    if pNode.right and pNode.right.left == None and pNode.right.right == None and pNode.right.val < limit:
                        pNode.right = None

                    stack.pop()
                    prev = pNode
                    pNode = None
                else:
                    pNode = pNode.right
        # self.show(root)

        # 将节点的值从和还原到之前单个节点的值，还是得后续遍历，将子节点得值需要父节点得值取还原
        stack =[]
        pNode, prev = root, None
        while len(stack) or pNode:
            if pNode:
                stack.append(pNode)
                pNode = pNode.left
            else:
                pNode = stack[-1]
                if pNode.right == None or pNode.right == prev:
                    if pNode.left and self.is_leaf(pNode.left) and id(pNode.left) not in leaf_node_id_dict:
                        pNode.left = None
                    if pNode.right and self.is_leaf(pNode.right) and id(pNode.right) not in leaf_node_id_dict:
                        pNode.right = None
                    if pNode.left:
                        pNode.left.val -= pNode.val
                    if pNode.right:
                        pNode.right.val -= pNode.val
                    prev = pNode
                    pNode = None
                    stack.pop()
                else:
                    pNode = pNode.right

        if  root and root.left is None and root.right is None and root.val < limit:
            return None
        else:
            return root

    def is_leaf(self,node):
        if node.left is None and node.right is None:
            return True
        else:
            return False

    def show(self, root):
        result = []
        from collections import deque
        queue = deque()
        queue.append(root)
        while (len(queue)):
            # print("a")
            length = len(queue)
            line = []
            for i in range(length):
                node = queue.popleft()
                line.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(line)
        print(result)