#|【Leetcode程序员面试金典】面试题04.06.后继者 leetcode|树

【#|【Leetcode程序员面试金典】面试题04.06.后继者】
文章目录

面试题04.06
- 1.问题描述
- 2.解决方案
- - 解法一：非递归分情况讨论法(代码实现有两种方式)
  - - a.方式一:找第一个左儿子是从p往上找getParent()
    - b.方式二:找第一个左儿子是从root往下找
  - 解法二：递归法

面试题04.06 1.问题描述

文章图片

2.解决方案
解法一：非递归分情况讨论法(代码实现有两种方式)

文章图片

a.方式一:找第一个左儿子是从p往上找getParent()

//分情况讨论正确写法 class Solution {public: TreeNode* getParent(TreeNode* root,TreeNode* p){if(root==p) return nullptr; queue q; q.push(root); while(q.empty()== false){TreeNode* t=q.front(); q.pop(); if(p==t->left||p==t->right) return t; if(t->left!= nullptr) q.push(t->left); if(t->right!= nullptr) q.push(t->right); } return nullptr; } TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {if(root== nullptr) return nullptr; if(root!= nullptr&&p== nullptr) return nullptr; //1.如果p节点有右子树，返回右子树最左边节点 if(p->right!= nullptr){TreeNode* t=p->right; while(t->left!= nullptr){t=t->left; } return t; }//2.如果p没有右子树 if(p->right== nullptr) {//2.1 p没有右子树且p是父亲的左儿子，返回p的父亲节点 TreeNode* parent=getParent(root,p); if(parent== nullptr||parent->left==p) return parent; //2.2 p没有右子树且p是父亲的右儿子，一直往上找，直到找到一个是父亲左儿子的节点结束，返回这个节点的父节点 if(parent->right==p){TreeNode* t=parent; while(t!= nullptr&&t->right==p){p=t; t=getParent(root,t); } //跳出循环代表t->left==p或者t==nullptr，故直接返回t return t; } }return nullptr; } };

b.方式二:找第一个左儿子是从root往下找

观察代码和上面的笔记图片分析代码的优越之处：在p没有右儿子的情况下root往下找的过程中，只有往左出溜(往左边找的时候)才会改变res也就是最后的结果，往右找的时候根本不改变res，这正好符合思路，这代码漂亮！

class Solution {public: TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {if (p->right) {p = p->right; while (p->left) p = p->left; return p; } TreeNode* res = NULL; while (root != p) {if (root->val < p->val) {root = root->right; } else {res = root; root = root->left; } } return res; } };

解法二：递归法

1.递归到右子树实则无法确定后继节点的位置，递归到右子树的最终结果也是递归到左子树
2.递归到左子树就能分情况讨论，最终得到结果，看着思路伪代码写出来的，有点难想！

文章图片

//递归法(思路在博客上) class Solution1 {public:TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {if(root== nullptr) return nullptr; if(root!= nullptr&&p== nullptr) return nullptr; //1.p大于或等于root,说明p后继节点在右子树,递归进右子树中 if(p->val>=root->val){return inorderSuccessor(root->right,p); }//2.p小于root,如果找到了那就在右子树中,如果找不到那后继就是root if(p->valval){TreeNode* ans=inorderSuccessor(root->left,p); if(ans== nullptr) ans=root; return ans; }return nullptr; } };