D16.ipynb

{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "",
   "id": "eddc4968041009a6"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 找树左下角的值  \n",
    "\n",
    "本题递归偏难，反而迭代简单属于模板题， 两种方法掌握一下 \n",
    "\n",
    "题目链接/文章讲解/视频讲解：https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html  \n"
   ],
   "id": "3744f6bb2e39a58f"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "BFS秒了  \n",
    "**递归**：\n",
    "1. 全局变量：最大深度，最深最左节点的值\n",
    "2. 递归参数：节点， 深度\n",
    "3. 递归操作：如果为叶节点，与最大深度比较：如果大于最大深度，说明是更深一层的最左节点，更新两个全局变量"
   ],
   "id": "b39a64b53e9343d6"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        self.max_depth = float('-inf')\n",
    "        self.result = None\n",
    "        self.traversal(root, 0)\n",
    "        return self.result\n",
    "    \n",
    "    def traversal(self, node, depth):\n",
    "        if not node.left and not node.right:\n",
    "            if depth > self.max_depth:\n",
    "                self.max_depth = depth\n",
    "                self.result = node.val\n",
    "            return\n",
    "        \n",
    "        if node.left:\n",
    "            self.traversal(node.left, depth+1)\n",
    "        if node.right:\n",
    "            self.traversal(node.right, depth+1)"
   ],
   "id": "5a4e791d2ffa2696"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 路径总和  \n",
    "\n",
    "本题 又一次涉及到回溯的过程，而且回溯的过程隐藏的还挺深，建议先看视频来理解 \n",
    "\n",
    "112. 路径总和，和 113. 路径总和ii 一起做了。 优先掌握递归法。\n",
    "\n",
    "题目链接/文章讲解/视频讲解：https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html  \n"
   ],
   "id": "70067a9e5636a073"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "递归：  \n",
    "1. 参数：节点，目标总和  \n",
    "2. 终止条件：目标总和等于当前节点值，且为叶节点\n",
    "3. 循环call：左子树or右子树，目标总和减去当前节点值\n"
   ],
   "id": "8ff9f05fe3b47e7e"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "class Solution:\n",
    "    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        if root.val == targetSum and root.left == root.right:\n",
    "            return True\n",
    "        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)"
   ],
   "id": "9e0e0a99902e12c8"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 113.路径总和II\n",
    "递归：  \n",
    "1. 参数：节点，目标总和，路径；没有返回值  \n",
    "2. 终止条件：目标总和等于当前节点值，且为叶节点，同时添加路径到结果集 \n",
    "3. 循环call：左子树or右子树，目标总和减去当前节点值\n",
    "4. 回溯：切记与赋值对称"
   ],
   "id": "392ed42d79bd6e03"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "\n",
    "        self.result = list()\n",
    "        self.helper(root, targetSum, [])\n",
    "        return self.result\n",
    "\n",
    "    def helper(self, root: Optional[TreeNode], targetSum: int, path: List[int]):\n",
    "        if not root:\n",
    "            return\n",
    "        path.append(root.val)\n",
    "        if root.val == targetSum and not root.left and not root.right:\n",
    "            self.result.append(list(path))\n",
    "        else:\n",
    "            self.helper(root.left, targetSum - root.val, path)\n",
    "            self.helper(root.right, targetSum - root.val, path)\n",
    "        path.pop() #在条件语句外，因为append在条件语句外"
   ],
   "id": "36dbb17cd1b1c0b4"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 从中序与后序遍历序列构造二叉树 \n",
    "\n",
    "本题算是比较难的二叉树题目了，大家先看视频来理解。 \n",
    "\n",
    "106.从中序与后序遍历序列构造二叉树，105.从前序与中序遍历序列构造二叉树 一起做，思路一样的\n",
    "\n",
    "题目链接/文章讲解/视频讲解：https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html \n",
    "\n",
    "\n"
   ],
   "id": "110c940a52978a62"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "中序遍历：\n",
    "1. 根节点左边的是左子树，右边的是右子树\n",
    "\n",
    "后序遍历：\n",
    "1. 最后访问的是根节点\n",
    "2. 倒数第二访问的是右子节点（如果有的话）  \n",
    "\n",
    "前序遍历：\n",
    "1. 最先访问的是根节点\n",
    "2. 第二访问的是左子节点（如果有的话）"
   ],
   "id": "5983202b13636edc"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 递归法：\n",
    "将每个节点的左右子树切开，进行递归"
   ],
   "id": "8a935f6b0285eb46"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(postorder) == 0:\n",
    "            return None\n",
    "        root = TreeNode(val = postorder[-1])\n",
    "        if len(postorder) == 1:\n",
    "            return root\n",
    "        index = inorder.index(postorder[-1])\n",
    "        root.left = self.buildTree(inorder[:index], postorder[:index])\n",
    "        root.right = self.buildTree(inorder[index+1:], postorder[index:len(postorder)-1])\n",
    "        return root"
   ],
   "id": "3ed61f1b526a4fc2"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 优化代码：\n",
    "- 将inorder的值和索引存入字典，减少查找时间  \n",
    "- 递归中先构建右子树，因为在pop后的postorder[-1]是右子节点（preorder相反）\n",
    "- **递归部分的参数是在inorder中的左子树和右子树的索引范围**：index是inorder的索引"
   ],
   "id": "8cca0ca3a701e84f"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        inorderIdx={v:i for i,v in enumerate(inorder)}\n",
    "\n",
    "        def helper(l,r):\n",
    "            if l==r:\n",
    "                return None\n",
    "            root=TreeNode(postorder.pop())\n",
    "            idx=inorderIdx[root.val]\n",
    "            root.right=helper(idx+1,r)\n",
    "            root.left=helper(l,idx)\n",
    "            return root\n",
    "\n",
    "        return helper(0,len(postorder))"
   ],
   "id": "e503c92312e5de47"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "前序和后序不能唯一确定一棵二叉树",
   "id": "3c25d66c52e1180c"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}