08-01-2019.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def repeatedNTimes(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        d = {}\n",
    "        \n",
    "        for a in A:\n",
    "            if a in d:\n",
    "                return a\n",
    "            d[a] = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution = Solution()\n",
    "solution.repeatedNTimes([2,1,2,5,3,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isUnivalTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        \n",
    "        vals = []\n",
    "        def inorder(root):\n",
    "            if root:\n",
    "                vals.append(root.val)\n",
    "                \n",
    "                temp = root.left\n",
    "                inorder(temp)\n",
    "\n",
    "                temp = root.right\n",
    "                inorder(temp)\n",
    "\n",
    "            return len(list(set(vals)))\n",
    "        \n",
    "        v = inorder(root)\n",
    "        #print(vals)\n",
    "        if v==1:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution = Solution()\n",
    "solution.isUnivalTree(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "root = TreeNode(1)\n",
    "root.left = TreeNode(1)\n",
    "root.right = TreeNode(1)\n",
    "root.left.left = TreeNode(1)\n",
    "root.left.right = TreeNode(1)\n",
    "root.right.right = TreeNode(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def diStringMatch(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        data = [i for i in range(len(S)+1)]\n",
    "        #print(data)\n",
    "        res = []\n",
    "        \n",
    "        for i in range(len(S)):\n",
    "            if S[i]== 'I':\n",
    "                res.append(data.pop(0))\n",
    "            else:\n",
    "                res.append(data.pop())\n",
    "              \n",
    "        res.append(data.pop())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 2, 0, 1]"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution = Solution()\n",
    "solution.diStringMatch(\"DDI\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def mergeTrees(self, t1, t2):\n",
    "        \"\"\"\n",
    "        :type t1: TreeNode\n",
    "        :type t2: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        \n",
    "        def dfs(h1,h2):\n",
    "            if h1==None and h2==None:\n",
    "                return None\n",
    "            elif h2 is None:\n",
    "                return h1\n",
    "            elif h1 is None:\n",
    "                return h2\n",
    "            \n",
    "            m=TreeNode(h1.val+h2.val)\n",
    "            print(m.val)\n",
    "            m.left=dfs(h1.left,h2.left)\n",
    "            m.right=dfs(h1.right,h2.right)\n",
    "            \n",
    "            return m\n",
    "        \n",
    "        m=dfs(t1,t2)\n",
    "\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [],
   "source": [
    "root1 = TreeNode(1)\n",
    "root1.left = TreeNode(3)\n",
    "root1.right = TreeNode(2)\n",
    "root1.left.left = TreeNode(5)\n",
    "\n",
    "root2 = TreeNode(2)\n",
    "root2.left = TreeNode(1)\n",
    "root2.right = TreeNode(3)\n",
    "root2.left.right = TreeNode(4)\n",
    "root2.right.right = TreeNode(7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inorder(root):\n",
    "    if root:\n",
    "        temp = root.left\n",
    "        inorder(temp)\n",
    "\n",
    "        print(root.val)\n",
    "        \n",
    "        temp = root.right\n",
    "        inorder(temp)\n",
    "\n",
    "    return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "4\n",
      "4\n",
      "3\n",
      "5\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "inorder(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "4\n",
      "5\n",
      "<__main__.TreeNode object at 0x000001ED62E67588>\n"
     ]
    }
   ],
   "source": [
    "solution = Solution()\n",
    "m = solution.mergeTrees(root1,root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root, val):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type val: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        \n",
    "        if root == None: return \n",
    "        if root.val == val:\n",
    "            return root\n",
    "        \n",
    "        if val<root.val:\n",
    "            return self.searchBST(root.left,val)\n",
    "        else:\n",
    "            return self.searchBST(root.right,val)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hgfdsa\n"
     ]
    }
   ],
   "source": [
    "s = \"asdfgh\"\n",
    "print(s[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node(object):\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution(object):\n",
    "    def postorder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: Node\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        if root is None:\n",
    "            return []\n",
    "        \n",
    "        ans = []\n",
    "        stk = []\n",
    "        stk.append(root)\n",
    "        \n",
    "        while stk:\n",
    "            temp = stk.pop()\n",
    "            ans.append(temp.val)\n",
    "            stk.extend(temp.children)\n",
    "            \n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node(object):\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution(object):\n",
    "    def preorder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: Node\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        if root is None:\n",
    "            return []\n",
    "        \n",
    "        ans = []\n",
    "        stk = []\n",
    "        stk.append(root)\n",
    "        \n",
    "        while stk:\n",
    "            temp = stk.pop()\n",
    "            ans.append(temp.val)\n",
    "            stk.extend(temp.children[::-1])\n",
    "            \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}