# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.maxdepth = float('-inf')  # 实例变量，可共享到traversal函数中，设置初始值为无穷小
        self.result = None
        self.traversal(root, 0)  # 根节点的深度为0或者1好像都不影响
        return self.result       # 返回最大深度对应的叶子节点的值


    def traversal(self, node, depth):
        """这里是递归+回溯+左右，其实层序法更简单"""
        if node.left == None and node.right == None:  # 叶子节点，若深度大于设定的最大深度，则更新最大深度
            if depth > self.maxdepth:
                self.maxdepth = depth
                self.result = node.val
            return      # 因为self.result是实例变量，所以是与findBottomLeftValue同步的，不用返回值
        # 如果不是叶子节点，就向下递归，先左子树再右子树，所以要加个回溯
        if node.left:
            depth += 1     # 向下，深度增大
            self.traversal(node.left, depth)
            depth -= 1     # 回溯
        if node.right:
            depth+=1
            self.traversal(node.right, depth)
            depth -= 1
        
        

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def hasPathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: bool
        """
        if not root:
            return False
        return self.traversal(root, targetSum-root.val)   # 注意代入的是 target-node.val

    def traversal(self, node, count):
        # 如果是叶子节点，当target减为0符合题目要求返回True
        if node.left == None and node.right == None:
            if count == 0:
                return True
            else:
                return False
        # 递归法，先左后右，不处理根，要回溯
        if node.left:
            count -= node.left.val
            if self.traversal(node.left, count): # 递归中代入的也是 target-node.val
                return True                      # 如果此节点满足要求，则向上传递True
            count += node.left.val
        if node.right:
            count -= node.right.val
            if self.traversal(node.right, count):
                return True
            count += node.right.val
        return False

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        # 第一步：递归终止条件1：
        if not postorder:
            return None
        
        # 第二步：从前序或者后序（左右根）入手，找到根节点的值，并建立目标二叉树
        root_val = postorder[-1]
        root = TreeNode(root_val)

        # 第三步：根据根节点的值，找到中序对应位置
        separator_idx = inorder.index(root_val)
        
        # 第四步：中序是左根右，所以可用根节点位置划分，得到左中序（中序排列时的左子树）、右中序
        left_inorder = inorder[:separator_idx]
        right_inorder = inorder[separator_idx+1:]

        # 第五步：回到后序（左右根），根据左子树和右子树的长度，得到左后序（后序排列时的左子树）、右后序
        left_postorder = postorder[:len(left_inorder)]
        right_postorder = postorder[len(left_inorder):-1]

        # 第六步：递归，再分别探究左子树的中序、后序，右子树的中序、后序
        root.left = self.buildTree(left_inorder, left_postorder)
        root.right = self.buildTree(right_inorder, right_postorder)

        # 返回二叉树
        return root