A-剑指offer/剑指 Offer 08. 二叉树的下一个节点.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "题目： 给定一颗二叉树和其中的一个节点，找出中序遍历的下一个节点。节点中除了有指向左右子节点的指针，还有指向父节点的指针"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "    def __str__(self):\n",
    "        ret = \"val=%d \" % self.val\n",
    "        if self.left!=None:\n",
    "            ret += \"left.val = %d \" % self.left.val\n",
    "        else:\n",
    "            ret += \"left=None \"\n",
    "        if self.right!=None:\n",
    "            ret += \"right.val=%d \" % self.right.val\n",
    "        else:\n",
    "            ret += \"right=None \"\n",
    "        if self.parent!=None:\n",
    "            ret += \"parent.val=%d \" % self.parent.val\n",
    "        else:\n",
    "            ret += \"parent=None \"\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "val=1 left.val = 2 right.val=3 parent=None \n",
      "val=2 left.val = 4 right.val=5 parent.val=1 \n",
      "val=3 left.val = 6 right.val=7 parent.val=1 \n"
     ]
    }
   ],
   "source": [
    "a = TreeNode(1)\n",
    "b = TreeNode(2)\n",
    "c = TreeNode(3)\n",
    "a.left = b\n",
    "a.right = c\n",
    "b.parent = a\n",
    "c.parent = a\n",
    "\n",
    "d = TreeNode(4)\n",
    "e = TreeNode(5)\n",
    "b.left = d\n",
    "b.right = e\n",
    "d.parent = b\n",
    "e.parent = b\n",
    "\n",
    "f = TreeNode(6)\n",
    "g = TreeNode(7)\n",
    "c.left = f\n",
    "c.right = g\n",
    "f.parent = c\n",
    "g.parent = c\n",
    "\n",
    "h = TreeNode(8)\n",
    "i = TreeNode(9)\n",
    "e.left = h\n",
    "e.right = i\n",
    "h.parent = e\n",
    "i.parent = e\n",
    "\n",
    "print(a)\n",
    "print(b)\n",
    "print(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    '''\n",
    "    root: 树的根节点\n",
    "    p: 要找到p节点的中序遍历的下一个界定啊\n",
    "    '''\n",
    "    def findNextNode(self, root: TreeNode, p: TreeNode)->TreeNode:\n",
    "        pNext = None\n",
    "        if root is None or p is None:\n",
    "            return None\n",
    "        \n",
    "        # 如果p有右子节点，则它的下一个节点是右子节点\n",
    "        if p.right != None:\n",
    "            pNext = p.right\n",
    "        else:\n",
    "            par = p.parent\n",
    "            # 如果parent是None说明p是根节点，又没有右子节点，则返回None\n",
    "            if par == None:\n",
    "                pNext = None\n",
    "            # 如果是父节点的左子节点，则下一个节点是父节点\n",
    "            elif par.left == p:\n",
    "                pNext = par\n",
    "            # 如果是父节点的右子节点，则下一个节点向上追溯，直到某一个节点是其父节点的左子节点，则该节点的父节点即为所求\n",
    "            elif par.right == p:\n",
    "                current = p\n",
    "                pare = par\n",
    "                while pare!=None and current==pare.right:\n",
    "                    current = pare\n",
    "                    pare = pare.parent\n",
    "                pNext = pare\n",
    "        return pNext"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "val=5 left.val = 8 right.val=9 parent.val=2 \n"
     ]
    }
   ],
   "source": [
    "s = Solution()\n",
    "p = s.findNextNode(a, b)\n",
    "print(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "val=1 left.val = 2 right.val=3 parent=None \n"
     ]
    }
   ],
   "source": [
    "print(s.findNextNode(a, i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "val=5 left.val = 8 right.val=9 parent.val=2 \n"
     ]
    }
   ],
   "source": [
    "print(s.findNextNode(a, h))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "val=3 left.val = 6 right.val=7 parent.val=1 \n"
     ]
    }
   ],
   "source": [
    "print(s.findNextNode(a, f))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "print(s.findNextNode(a, g))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}