好大夫 网站开发,在网站接入银联怎么做,精品资料网资料大全,交互比较好的网站文本目录#xff1a;
❄️一、习题一(前序遍历非递归)#xff1a; ▶ 思路#xff1a; ▶ 代码#xff1a; ❄️二、习题二(中序遍历非递归)#xff1a; ▶ 思路#xff1a; ▶ 代码#xff1a; ❄️三、习题三(后序遍历非递归)#xff1a; ▶ 思路#xff1a; …文本目录
❄️一、习题一(前序遍历非递归) ▶ 思路 ▶ 代码 ❄️二、习题二(中序遍历非递归) ▶ 思路 ▶ 代码 ❄️三、习题三(后序遍历非递归) ▶ 思路 ▶ 代码 ❄️四、习题四(选择题) ➷ 选则题一 ➷ 选则题二 ➷ 选则题三 ➷ 选则题四 ➷ 选则题五
❄️五、总结 ❄️一、习题一(前序遍历非递归) ☞ 题的链接 前序遍历非递归 ▶ 思路 对于这道题呢我们不使用递归实现我们呢需要使用到一种结构——栈。来实现这个前序遍历的操作因为返回的 ListInteger 我们呢要把每次的节点的 val 值存放到 List 里面。 我们先把根节点放入到栈中之后遍历左子树把其都放到栈中当 cur 为空的时候出栈顶节点给到 top 这个临时变量中把 top.right 给到 cur 节点并且我们每次入栈的节点的值都要放到List 当中最后返回的是 List 这个数据结构。 我们来看看图是如何进行的
OK这个呢就是我们这个题的操作流程了我们来看看代码是如何编写的 ▶ 代码
public ListInteger preorderTraversal(TreeNode root) {ListInteger ret new LinkedList();if (root null) {return ret;}StackTreeNode stack new Stack();//先把根节点入进来TreeNode cur root;while (cur ! null || !stack.isEmpty()) {while (cur ! null) {//入Listret.add(cur.val);//入栈stack.push(cur);//往左子树遍历cur cur.left;}//存储栈顶节点TreeNode top stack.pop();//把栈顶的节点的右子树给到curcur top.right;}return ret;}
我们的前序遍历的非递归就到这结束了当然有前序就得有 中序和后序我们来看看。 ❄️二、习题二(中序遍历非递归) ☞ 题的链接 中序遍历的非递归实现 ▶ 思路 对于我们这个题呢当我们了解了上面的代码之后呢就是非常好写了我们对于前序遍历是
根 左 右。我们的中序遍历呢是 左 根 右。所以呢这个题其实就很简单了我们只需要把我们存储到 List 的代码改变到我们出栈顶数据之后再存储到 List 当中并且我们要注意我们存储到List 的 val 值应该是我们出的栈顶的数据 top 的 val 值。 我们的代码流程和上面的题是差不多的我们只需要改变 List 的存储顺序就可以了。 我们来看看代码如何编写 ▶ 代码
public ListInteger inorderTraversal(TreeNode root) {ListInteger ret new LinkedList();if (root null) {return ret;}StackTreeNode stack new Stack();TreeNode cur root;while (cur ! null || !stack.isEmpty()) {while (cur ! null) {stack.push(cur);cur cur.left;}TreeNode top stack.pop();//我们在这里进行存储到 List 中ret.add(top.val); cur top.right;}return ret;} ❄️三、习题三(后序遍历非递归) ☞ 题的链接 后序遍历的非递归实现 ▶ 思路 后序遍历是左 右 根。我们这个题的代码呢和前面两个遍历是不一样的这个呢我们需要判断左子树和右子树都为空的情况下才能把这个节点的值存到 List 当中所以我们不是先出栈我们需要先 peek 一下栈顶的数据看是否栈顶数据的右子树是否为空为空则打印不为空就把其右子树的节点放到 cur 中 。但是如果这样写呢会有一些问题我们一会在看我们下把我们描述的代码写下
public ListInteger postorderTraversal(TreeNode root) {ListInteger ret new LinkedList();if (root null) {return ret;}StackTreeNode stack new Stack();TreeNode cur root;while(cur ! null || !stack.isEmpty()) {while(cur ! null) {stack.push(cur);cur cur.left;}TreeNode top stack.peek();if (top.right null) {ret.add(top.val);stack.pop();}else {cur top.right;}}return ret;}
我们来看看这个代码哪里存在问题呢 所以我们需要一个临时变量用来存储我们要出栈的节点当我们再次循环的时候如果 top.right prev 这个节点就不会进入出栈的方法中。
那么我们来看看最终的代码是什么样的 ▶ 代码
public ListInteger postorderTraversal(TreeNode root) {ListInteger ret new LinkedList();if (root null) {return ret;}StackTreeNode stack new Stack();TreeNode cur root;TreeNode prev null;while (cur ! null || !stack.isEmpty()) {while (cur ! null) {stack.push(cur);cur cur.left;}TreeNode top stack.peek();if (top.right null || top.right prev) {ret.add(top.val);stack.pop();prev top;} else {cur top.right;}}return ret;} 到这里呢我们关于我们前中后序的非递归遍历就到这里就结束了我们呢之后来看看几道选择题这几次做代码题是不是都做腻了我们来看看新口味选择题。 也是关于二叉树的。 ❄️四、习题四(选择题) ➷ 选则题一 某二叉树共有 399 个节点其中 199 个度为 2 的节点则该二叉树中叶子节点数为 ( ) A、不存在这样的二叉树 B、200 C、198 D、199 这个选择题呢我们使用到的公式是 n0(度为0的节点个数) n2(度为2的节点的个数) 1
这样之后我们这个题就好做了我们的 叶子节点就是度为0 的节点所以这个题中的叶子节点数为n0 199 1 200 个所以这题我们选择 B。 ➷ 选则题二 在具有 2n 个节点的完全二叉树中叶子结点的个数为 ( ) A、n B、n 1 C、n - 2 D、n / 2 这道题呢我们呢要考虑这个总结点个数呢是奇数还是偶数的情况下是不一样的结果的。我们的总结点是n0 n1 n2 这些节点的总数。 当我们的总结点个数为偶数的时候呢我们的 n1 为 1 当我们的总结点的个数为奇数的时候呢我们的 n1 是 0。
注意这道题我们还是需要借助 n0 n2 1 这个公式 我们再来看看总结点数为奇数的情况是什么样的 我们再回到这道题中我们的总结点数为 2n 是偶数所以这里我们使用偶数的情况进行计算
就可以得出我们的 叶子结点(n0) 是 n 个。 ➷ 选则题三
我们来举一个总结点数为奇数的情况是什么样的 一个总结点为 767 个节点的完全二叉树其 叶子节点 个数为 ( ) A、383 B、384 C、385 D、386 我们来看看这道题是怎样做的我们的这个题的节点数为 767 是奇数个所以我们使用 奇数的节点个数来计算 叶子节点。 767 n0 n2 767 n0 n0 - 1 766 2n0 n0 383 由此可知我们这个题的 叶子节点 的个数就是 383 个。所以我们选择 A。 ➷ 选则题四 接下来我们来看看对于遍历的题 设一颗二叉树的中序遍历为badce后序遍历为bdeca则二叉树的前序遍历是什么 ( ) A、adbce B、decab C、debca D、abcde 这种题呢我们需要记住 前中后序 遍历的顺序用给的两个遍历呢去还原二叉树之后再遍历我们需要的那个二叉树就可以了。 我们来看看这道题 我们的 后序遍历是左 右 根所以我们的后序遍历的最后一个值就是根节点之后到中序遍历左 根 右去寻找根节点把左子树和右子树分割出来再去后序遍历中寻找 右子树的根节点再到中序中寻找循环执行这个操作直至后序没有节点这个呢就是我们的上个博客中的编码题变成了我们的选择题。 这个就是这个题的二叉树了之后我们再对其进行前序遍历就可以了最后我们的到 前序遍历为abcde。所以这道题就选择 D。 ➷ 选则题五 某二叉树的后序遍历和中序遍历的序列是相同的均为ABCDEF则按照 层序遍历是 ( ) A、FEDCBA B、CBAFED C、DEFCBA D、ABCDEF 这道题呢我们要知道我们的 后序遍历是 左 右 根。中序遍历是左 根 右。 他们的遍历顺序是不同的所以要是想要它们的遍历循序是一样的话我们的右子树是没有节点的这样呢结果就可以是一样的了当我们的右子树为空后序遍历就是先左再根。中序遍历就是先左再根。就是一样的了。比如这道题的二叉树就可以得到这样的
所以我们可以得知我们的层序遍历在这里就是FEDCBA 。所以这道题我们选择 A。 ❄️五、总结 OK我们的这个关于我们的二叉树的习题三但这里就结束了同时到这里呢我们的
数据结构 ——二叉树 也就结束了之后呢我们进入到新的章节了欲知后事如何且听下回分说
拜拜啦~~~我们下篇博客再见。
