手撕二叉树
2018-08-19 本文已影响1人
熊大状
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
与二叉树相关的代码有大量的指针操作，在每次使用指针的时候，需要判断指针是否是nullptr，以及该如何处理。
【面试题06：重建二叉树】
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：根据前序找到根节点，然后在中序中找到左右根序列，递归。采用vector装序列，即每次递归更新前序vector和中序vector。如果是python，可利用list的切片。
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.empty() || vin.empty()) return nullptr;
vector<int>left_pre,left_vin,right_vin,right_pre;
int rootValue = pre[0];
//创建根节点
TreeNode* root = new TreeNode(rootValue);
int m = 0;
while(m+1<vin.size() && vin[m] != rootValue){
left_pre.push_back(pre[m+1]);
left_vin.push_back(vin[m]);
m++;
} //更新左子树的前序、中序。
while(m+1<vin.size()){
right_pre.push_back(pre[m+1]);
right_vin.push_back(vin[m+1]);
m++;
}//更新右子树的前序和中序
//重建左子树
root->left = reConstructBinaryTree(left_pre,left_vin);
//重建右子树
root->right = reConstructBinaryTree( right_pre,right_vin);
//返回重建二叉树
return root;
}
};
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
if len(pre) == 0 or len(tin) == 0:
return None
root = TreeNode(pre[0])
m = 0
#找到中序中根节点的位置m
while tin[m] != pre[0]:
m += 1
##利用list的切片，直接更新左右子树前序、中序
root.left = self.reConstructBinaryTree(pre[1:m+1],tin[:m])
root.right = self.reConstructBinaryTree(pre[m+1:],tin[m+1:])
return root
【面试题58：二叉树的下一个结点】
题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路：分两种情况：1）节点存在右子树；2）不存在右子树，又分两种：a)遍历父节点，能找到父节点的左子节点是本身的节点；b)不存在a)中节点。
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode == nullptr) return nullptr;
TreeLinkNode* pNext = nullptr;
if(pNode->right != nullptr){
pNext = pNode->right;
while(pNext->left != nullptr)
pNext = pNext->left;
}//情况一：结点存在右子树
else if(pNode->next != nullptr){
TreeLinkNode* pParent = pNode;
//情况二：结点不存在右子树，并不是根节点。
//同时寻找父节点的左结点是本身的结点。
while(pParent->next != nullptr
&& pParent->next->left != pParent)
pParent = pParent->next;
//协议节点为该节点的父节点，如不存在即为根节点的父节点nullptr
pNext = pParent->next;
}
return pNext;
}
};
【面试题19：树的子结构】Subtree of Another Tree
题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）。注意题目子结构的定义：1）存在即可；2）存在即左右子树全部一样。
思路：两步：1）找到相同根节点，然后递归判断左右子树，返回结果；2）递归左右子树找到下一个相同根节点。
####子结构定义：
3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.
class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if(s == nullptr || t == nullptr) return false;
bool result = false;
if(s->val == t->val)
result = JudgeSubTree(s,t);
if(!result)
result = isSubtree(s->left, t);
if(!result)
result = isSubtree(s->right, t);
return result;
}
bool JudgeSubTree(TreeNode* s, TreeNode* t) {
if(s == nullptr && t == nullptr) return true;
if(t == nullptr || s == nullptr) return false;
if(s->val != t->val) return false;
return JudgeSubTree(s->left,t->left) && JudgeSubTree(s->right, t->right);
}
};
【面试题19：二叉树的镜像】
题目：完成一个函数，输入一个二叉树，该函数输出它的镜像。
思路：左右子树交换。
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if(pRoot == nullptr) return;
if(pRoot->left == nullptr && pRoot->right == nullptr)
return ;
TreeNode* temp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = temp;
Mirror(pRoot->left);
Mirror(pRoot->right);
}
};
【面试题59：对称的二叉树】
题目：请实现一个函数来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
思路：1）求出二叉树的镜像，然后判断是否与原二叉树相等。具体：将根节点的左子树镜像，然后与右子树相比。
2）采用遍历思想，对称即左和右可以交换，以前序遍历为例，根左右和根右左应该是相等的。
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
return isSymmetricalTree(pRoot,pRoot);
}
bool isSymmetricalTree(TreeNode* pRoot1,TreeNode* pRoot2){
if(pRoot1 == nullptr && pRoot2 == nullptr)
return true;
if(pRoot1 == nullptr || pRoot2 == nullptr)
return false;
if(pRoot1->val != pRoot2->val)
return false;
return isSymmetricalTree(pRoot1->left, pRoot2->right)
&& isSymmetricalTree(pRoot1->right, pRoot2->left);
}
};
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root == nullptr || (root->left ==nullptr && root->right == nullptr))
return true;
TreeNode* leftTree = Mirror(root->left);
return isSameTree(leftTree, root->right);
}
###递归代码的理解，如函数需要返回根节点：
TreeNode* Mirror(TreeNode* pRoot){
if(pRoot == nullptr)
return nullptr;
if(pRoot->left == nullptr && pRoot->right == nullptr)
return pRoot;
TreeNode* temp = pRoot->left;
pRoot->left = Mirror(pRoot->right);
pRoot->right = Mirror(temp);
return pRoot;
}
bool isSameTree(TreeNode* t1, TreeNode* t2){
if(t1 == nullptr && t2 == nullptr)
return true;
if(t1 == nullptr || t2 == nullptr) return false;
if(t1->val != t2->val)
return false;
return isSameTree(t1->left, t2->left) && isSameTree(t1->right, t2->right);
}
};
【面试题23：从上往下打印二叉树】
题目：从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路：利用队列前出后进操作，逐层遍历push进队列。
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
if(root == nullptr) return {};
vector<int>result;
deque<TreeNode*>dequeOrder;
dequeOrder.push_back(root);
while(dequeOrder.size()){
TreeNode *curNode = dequeOrder.front();
result.push_back(curNode->val);
dequeOrder.pop_front();
if(curNode->left)
dequeOrder.push_back(curNode->left);
if(curNode->right)
dequeOrder.push_back(curNode->right);
}
return result;
}
};
【面试题24：二叉搜索树的后序遍历序列】
题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路：找出根节点，然后遍历序列，找到左右子树，然后递归，不满足条件即返回false。
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.empty()) return false;
int root = sequence[sequence.size()-1];
int i = 0;
vector<int> left,right;
while(i<sequence.size()-1 && sequence[i]<root)
left.push_back(sequence[i++]);
while(i<sequence.size()-1 && sequence[i]>root)
right.push_back(sequence[i++]);
if(i != sequence.size()-1) return false;
bool isLeft = true, isRight = true;
if(!left.empty())
isLeft = VerifySquenceOfBST(left);
if(!right.empty())
isRight = VerifySquenceOfBST(right);
return isLeft && isRight;
}
};
【面试题25：二叉树中和为某一值的路径】
题目：输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
思路：遍历二叉树，采用前序，即先访问根节点进行操作，然后递归左右子树。具体来说：访问当前节点若为叶节点且满足和相等，则打印或push_back，然后递归左右子树。不管怎么样到达叶节点，需要pop_back，返回父节点。
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>>pathAll;
if(root == nullptr)
return pathAll;
vector<int>path;
pathFind(root,sum,path,pathAll,0);
return pathAll;
}
void pathFind(TreeNode* root, int sum, vector<int>path,
vector<vector<int>> &pathAll, int curSum){
bool isLeaf = root->left == nullptr && root->right == nullptr;
curSum += root->val;
path.push_back(root->val);
if(curSum == sum && isLeaf){
pathAll.push_back(path);
}
if(root->left != nullptr)
pathFind(root->left,sum,path,pathAll,curSum);
if(root->right != nullptr)
pathFind(root->right,sum,path,pathAll,curSum);
path.pop_back();
}
};
【面试题27：二叉搜索树与双向链表】
题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：由于是二叉搜索树，其中序遍历即为最后链表排序顺序，然后剩下来的工作就是指针的转换操作。定义一个指针指向已经转好的链表的最后一个节点。当前节点left指向定义节点，定义节点right指向当前节点，然后定义节点更新成当前节点。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
ConvertNode(pRootOfTree);
TreeNode* pHead = pNode;
while(pHead != nullptr && pHead->left != nullptr)
pHead = pHead->left;
return pHead;
}
void ConvertNode(TreeNode* pRoot){
if(pRoot != nullptr){
//访问左子树
ConvertNode(pRoot->left);
//访问节点pRoot，为中序遍历节点，进行指针操作。
pRoot->left = pNode;
if(pNode != nullptr)
pNode->right = pRoot;
pNode = pRoot;
//访问右子树
ConvertNode(pRoot->right);
}
}
private:
TreeNode* pNode = nullptr;
};
【面试题60：把二叉树打印出多行】
【面试题61：按之字形顺序打印二叉树】
【面试题62：序列化二叉树】
【面试题63：二叉搜索树的第k个结点】
题目：给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
思路：中序遍历，如果满足k == 1 则返回此时节点。
class Solution {
public:
TreeNode* KthNode(TreeNode* pRoot, int k)
{
TreeNode* kthNode = nullptr;
InOrder(pRoot,k,&kthNode);
return kthNode;
}
void InOrder(TreeNode* pRoot, int &k, TreeNode** kthNode){
if(pRoot != nullptr){
InOrder(pRoot->left, k, kthNode);
if(k-- == 1){
*kthNode = pRoot;
return ;
}
InOrder(pRoot->right, k, kthNode);
}
}
};
//带返回值的递归
class Solution {
int count = 0; //引入成员变量,如果k是值传递的话。
public:
TreeNode* KthNode(TreeNode* pRoot, unsigned int &k)
{//k为引用传递
if(pRoot){
TreeNode *ret = KthNode(pRoot->left, k);
if(ret) return ret; // 左子树找的到第k个，则temp不为nullptr，返回temp
if(--k == 0) return pRoot; // 如果满足条件，返回proot（不为nullptr）
ret = KthNode(pRoot->right,k);
if(ret) return ret;//同理
}//如果找不到，则一直遍历，最后返回nullptr。
return nullptr;
}
};
【面试题39：二叉树的深度】
题目：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
拓展：平衡二叉树的判断。
思路：深度计算为左右子树去较大值+1，进而递归左右子树累加深度。判断平衡二叉树，不仅需要计算左右子树的深度，而且还要判断是否平衡，返回bool。进而增加一个引用，用于计算深度，函数返回是否平衡。
启发：一个函数存在多个变量需要返回时，可以增加函数参数（采用引用传递）。
class Solution {
public:
int TreeDepth(TreeNode* pRoot)
{//计算二叉树深度
if(pRoot == nullptr)
return 0 ;
int depthLeft = TreeDepth(pRoot->left);
int depthRight = TreeDepth(pRoot->right);
return depthLeft>depthRight? depthLeft+1: depthRight+1;
}
//判断平衡二叉树
bool IsBalanced_Solution(TreeNode* pRoot) {
int depth = 0;
return IsBalancedTree(pRoot,depth);
}
bool IsBalancedTree(TreeNode* pRoot, int &depth) {
if(pRoot == nullptr){
depth = 0;
return true;
}
int left, right;
if(IsBalancedTree(pRoot->left,left)
&& IsBalancedTree(pRoot->right,right)){
int diff = left -right;
if(diff<=1 && diff>=-1){
depth = left > right ? left+1 : right+1;
return true;
}
}
return false;
}
};
