《剑指offer》面试题8-二叉树的下一个结点

悠悠 2022-03-10 13:50 157阅读 0赞

# 一、题目 #

###         题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 ###

# 二、题目分析 #

### 分析二叉树的下一个节点有以下几种情况： ###

### 1、情况一：若该结点有右子树，则下一个节点为它的右子树中的最左子节点； ###

### 2、情况二：若该节点无右子树，且该节点为其父节点的左子节点，则其下一个节点为其父节点； ###

### 3、情况三：若该节点无右子树，且该节点为其父节点的右子节点，则沿着父节点向上遍历，直至遇到节点为其父节点的左子节点的节点，则其下一个节点就是该父节点。 ###

# 三、代码实现 #

#include <iostream>
    #include <string>
    #include <vector>
    #include <stack>
    using namespace std;
    struct BinaryTreeNode {
    	int value;//数值
    	BinaryTreeNode* parent;//父节点
    	BinaryTreeNode* left;//左孩子
    	BinaryTreeNode* right;//右孩子
    };
    
    //查找结点
    BinaryTreeNode* findnode(BinaryTreeNode* root,int e) {//在根结点为root的子树中查找值为e的结点
    	if (root == nullptr) {
    		return nullptr;
    	}
    	if (root->value == e) {
    		return root;
    	}
    	if (root->left) findnode(root->left, e);//递归深入左子树查找
    	if (root->right) findnode(root->right, e);//递归深入右子树查找
    }
    //查找二叉树的下一个节点
    int findNext(BinaryTreeNode* root, int e) {
    	BinaryTreeNode* this_node = findnode(root, e);//首先查找值为e的结点
    	if (this_node == nullptr) return -1;//若结点不存在则返回-1，表示无后继节点
    	if (this_node->right) {//若该结点存在右孩子，则其后继结点是右子树中的最左结点
    		BinaryTreeNode* p = this_node->right;
    		while (p->left) {
    			p = p->left;
    		}
    		return p->value;
    	}
    	else {//若该结点不存在右孩子
    		if (this_node->parent == nullptr) return -1;//若该结点且不存在父节点，则返回-1，表示无后继节点
    		if (this_node->parent->left == this_node) {//若该结点且为其父节点的左孩子，则父节点就是其后继节点
    			return this_node->parent->value;
    		}
    		else {//若该结点且为其父节点的右孩子，则需要沿着指向父节点的指针向上遍历，直至遇到一个是它父节点的左子节点的节点
    			BinaryTreeNode* p = this_node->parent;
    			while (p->parent) {
    				if (p->parent->left == p) {
    					return p->parent->value;
    				}
    				p = p->parent;
    			}
    			return -1;
    		}	 
    	}
    }

代码的优化版本：

//查找二叉树的下一个节点--优化版本
    int findNext2(BinaryTreeNode* root, int e) {
    	BinaryTreeNode* this_node = findnode(root, e);//首先查找值为e的结点
    	if (this_node == nullptr) return -1;//若结点不存在则返回-1，表示无后继节点
    	if (this_node->right) {//若该结点存在右孩子，则其后继结点是右子树中的最左结点
    		BinaryTreeNode* p = this_node->right;
    		while (p->left) {
    			p = p->left;
    		}
    		return p->value;
    	}
    	else {//若该结点不存在右孩子
    		if (this_node->parent == nullptr) return -1;//若该结点且不存在父节点，则返回-1，表示无后继节点
    		else {
    			BinaryTreeNode* p = this_node->parent;
    			BinaryTreeNode* pcurrent = this_node;
    			while (p != nullptr && pcurrent == p->right) {
    				//若该结点且为其父节点的右孩子，则需要沿着指向父节点的指针向上遍历，直至遇到一个是它父节点的左子节点的节点
    				//若该结点且为其父节点的左孩子，则父节点就是其后继节点
    				pcurrent = p;
    				p = p->parent;
    			}
    			return p ? p->value:-1;
    		}
    	}
    }