Leetcode DFS_面试题 04.06. 后继者

￡神魔★判官ぃ 2023-03-14 08:06 7阅读 0赞

### Leetcode DFS\_面试题 04.06. 后继者 ###

*  1、问题分析
 *  2、问题解决
 *  3、总结

# 1、问题分析 #

本质上就是一个二叉树的遍历问题，这里用`vector`数组存放遍历的值，找到就直接返回。

# 2、问题解决 #

笔者以C++方式解决。

#include "iostream"
    
    using namespace std;
    
    #include "algorithm"
    #include "vector"
    #include "math.h"
    
    struct TreeNode { 
    	int val;
    	TreeNode *left;
    	TreeNode *right;
    
    	TreeNode(int x) : val(x), left(NULL), right(NULL) { 
    
    	}
    };
    
    class Solution { 
    public:
    	vector<TreeNode *> treeNodes;
    	int flag = 0;
    
    	TreeNode *inorderSuccessor(TreeNode *root, TreeNode *p) { 
    		if (root == NULL) { 
    			return NULL;
    		}
    		// 中序遍历
    		inorder(root, p);
    
    		for (int i = 0; i < treeNodes.size(); ++i) { 
    			if (treeNodes[i]->val == p->val) { 
    				if (i + 1 == treeNodes.size()) { 
    					return NULL;
    				}
    				else { 
    					return treeNodes[i + 1];
    				}
    			}
    		}
    
    		return NULL;
    	}
    
    	/** * 中序遍历 * @param root */
    	void inorder(TreeNode *root, TreeNode *p) { 
    		if (root == NULL) { 
    			return;
    		}
    
    		//再访问左子节点
    		inorder(root->left, p);
    
    
    		if (flag == 1) { 
    			flag = 2;
    		}
    
    		// 中序遍历
    		treeNodes.push_back(root);
    		if (flag == 2) { 
    			return;
    		}
    		if (root->val == p->val) { 
    			flag = 1;
    		}
    
    
    		//最后访问右子节点
    		inorder(root->right, p);
    	}
    };
    
    /** * 先序遍历 * @param root */
    void preorder(TreeNode *root) { 
    	if (root == NULL || root->val == -1) { 
    		return;
    	}
    	// 先访问根节点
    	cout << root->val << endl;
    	// 再访问左子节点
    	preorder(root->left);
    	// 最后访问右子节点
    	preorder(root->right);
    }
    
    /** * 根据数组创建二叉树 * @param a * @param n * @return */
    TreeNode *create(int a[], int n) { 
    	// 根据数组大小分配内存空间
    	TreeNode *ptree = (TreeNode *)malloc(sizeof(TreeNode) * n);
    	int i;
    	// 根据数组的值，依次给二叉树节点赋值
    	for (i = 0; i < n; i++) { 
    		// if (a[i] == -1) { 
    		// ptree[i] = NULL;
    		// continue;
    		// }
    		ptree[i].val = a[i];//数组a只起到一个赋值的作用
    		ptree[i].left = NULL;
    		ptree[i].right = NULL;
    	}
    	// 将数组中节点按照二叉树规则连接起来
    	for (i = 0; i <= n / 2 - 1; i++)//原来的父亲节点范围为1~n/2,现在0~n/2-1,所以注意n/2要取到等
    	{ 
    		if (2 * i + 1 <= n - 1)
    			ptree[i].left = &ptree[2 * i + 1];//把第2*i+1个结点的地址赋给左孩子
    		if (2 * i + 2 <= n - 1)
    			ptree[i].right = &ptree[2 * i + 2];
    	}
    	return ptree;
    }
    
    template<class T>
    
    /** * 获取数组长度 * @tparam T * @param array * @return */
    int getsize(T &array) { 
    	return sizeof(array) / sizeof(array[0]);
    }
    
    
    int main() { 
    	// int a[] = {5, 1, 4, -1, -1, 3, 6};
    	// int a[] = {2,1,3};
    	int a[] = {  10, 5, 15, -1, -1, 6, 20 };
    	// 创建二叉树
    	TreeNode *pNode = create(a, getsize(a));
    	// preorder(pNode);
    	Solution *pSolution = new Solution;
    	TreeNode *pTreeNode = pSolution->inorderSuccessor(pNode, pNode->right);
    	cout << pTreeNode->val << endl;
    	system("pause");
    	return 0;
    }

运行结果

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]

然后改进版可以不用数组存储值，只用一个变量，但是逻辑更加复杂，也就是时间会上去。

#include "iostream"
    
    using namespace std;
    
    #include "algorithm"
    #include "vector"
    #include "math.h"
    
    struct TreeNode { 
        int val;
        TreeNode *left;
        TreeNode *right;
    
        TreeNode(int x) : val(x), left(NULL), right(NULL) { 
    
        }
    };
    
    class Solution { 
    public:
        int flag = 0;
        TreeNode *ans = NULL;
    
        TreeNode *inorderSuccessor(TreeNode *root, TreeNode *p) { 
            if (root == NULL) { 
                return NULL;
            }
            // 中序遍历
            inorder(root, p);
    
            return ans;
        }
    
        /** * 中序遍历 * @param root */
        void inorder(TreeNode *root, TreeNode *p) { 
            if (flag == 3) { 
                return;
            }
            if (root == NULL) { 
                ans = NULL;
                return;
            }
    
            //再访问左子节点
            inorder(root->left, p);
    
            // 表明已经找到指定节点的下一个节点准备结束了
            if (flag == 1) { 
                flag = 2;
            }
    
            if (flag != 3) { 
                // 中序遍历
                ans = root;
            }
    
            // 已经找到指定节点的下一个节点可以结束了(这里放到ans中即可，直接返回)
            if (flag == 2) { 
                flag = 3;
                return;
            }
            //表明已经找到指定节点了
            if (root->val == p->val) { 
                flag = 1;
            }
    
    
            //最后访问右子节点
            inorder(root->right, p);
        }
    };
    
    /** * 先序遍历 * @param root */
    void preorder(TreeNode *root) { 
        if (root == NULL || root->val == -1) { 
            return;
        }
    // 先访问根节点
        cout << root->val << endl;
    // 再访问左子节点
        preorder(root->left);
    // 最后访问右子节点
        preorder(root->right);
    }
    
    /** * 根据数组创建二叉树 * @param a * @param n * @return */
    TreeNode *create(int a[], int n) { 
    // 根据数组大小分配内存空间
        TreeNode *ptree = (TreeNode *) malloc(sizeof(TreeNode) * n);
        int i;
    // 根据数组的值，依次给二叉树节点赋值
        for (i = 0; i < n; i++) { 
            // if (a[i] == -1) { 
            // ptree[i] = NULL;
            // continue;
            // }
            ptree[i].val = a[i];//数组a只起到一个赋值的作用
            ptree[i].left = NULL;
            ptree[i].right = NULL;
        }
    // 将数组中节点按照二叉树规则连接起来
        for (i = 0; i <= n / 2 - 1; i++)//原来的父亲节点范围为1~n/2,现在0~n/2-1,所以注意n/2要取到等
        { 
            if (2 * i + 1 <= n - 1)
                ptree[i].left = &ptree[2 * i + 1];//把第2*i+1个结点的地址赋给左孩子
            if (2 * i + 2 <= n - 1)
                ptree[i].right = &ptree[2 * i + 2];
        }
        return ptree;
    }
    
    template<class T>
    
    /** * 获取数组长度 * @tparam T * @param array * @return */
    int getsize(T &array) { 
        return sizeof(array) / sizeof(array[0]);
    }
    
    
    int main() { 
    // int a[] = {5, 1, 4, -1, -1, 3, 6};
    // int a[] = {2,1,3};
    // int a[] = {10, 5, 15, -1, -1, 6, 20};
        int a[] = { 5, 3, 6, 2, 4, -1, -1, 1};
    // 创建二叉树
        TreeNode *pNode = create(a, getsize(a));
    // preorder(pNode);
        Solution *pSolution = new Solution;
        TreeNode *pTreeNode = pSolution->inorderSuccessor(pNode, pNode->left->left->left);
        cout << pTreeNode->val << endl;
        system("pause");
        return 0;
    }

运行结果

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70 1]  
上面是有注释的，下面是没有注释的。所以提交的时候最好把注释去掉。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70 2]

有点菜，有时间再优化一下。

# 3、总结 #

书上的代码直接运行绝大部分是对的，但是总有一些软件的更新使得作者无能为力。之前的API是对的，但是之后就废弃了或修改了是常有的事。所以我们需要跟踪源代码。这只是一个小小的问题，如果没有前辈的无私奉献，很难想象我们自己一天能学到多少内容。感谢各位前辈的辛勤付出，让我们少走了很多的弯路！

点个赞再走呗！欢迎留言哦！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]: /images/20230312/5208224c856a47debf9f4207e167b400.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70 1]: /images/20230312/98d06b7f8073411b86c963e9cbd1dc19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70 2]: /images/20230312/9cdfb4d4c6754f0cbd1440123688787c.png