Java-数据结构-二叉树-习题(三) ￣へ￣
文本目录：
❄️一、习题一(前序遍历非递归)：
☞ 题的链接：
▶ 思路：
对于这道题呢，我们不使用递归实现，我们呢需要使用到一种结构——栈。来实现这个前序遍历的操作，因为返回的 List<Integer> 我们呢要把每次的节点的 val 值存放到 List 里面。
我们先把根节点放入到栈中，之后遍历左子树把其都放到栈中，当 cur 为空的时候，出栈顶节点给到 top 这个临时变量中，把 top.right 给到 cur 节点，并且我们每次入栈的节点的值都要放到List 当中最后返回的是 List 这个数据结构。
我们来看看图是如何进行的：
OK，这个呢就是我们这个题的操作流程了，我们来看看代码是如何编写的：
▶ 代码：
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new LinkedList<>();
if (root == null) {
return ret;
}
Stack<TreeNode> stack = new Stack<>();
//先把根节点入进来
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
//入List
ret.add(cur.val);
//入栈
stack.push(cur);
//往左子树遍历
cur = cur.left;
}
//存储栈顶节点
TreeNode top = stack.pop();
//把栈顶的节点的右子树给到cur
cur = top.right;
}
return ret;
}我们的前序遍历的非递归就到这结束了，当然有前序就得有 中序和后序，我们来看看。
❄️二、习题二(中序遍历非递归)：
☞ 题的链接：
▶ 思路：
对于我们这个题呢，当我们了解了上面的代码之后呢，就是非常好写了，我们对于前序遍历是：
根 左 右。我们的中序遍历呢是： 左 根 右。所以呢这个题其实就很简单了，我们只需要把我们存储到 List 的代码，改变到我们出栈顶数据之后再存储到 List 当中，并且我们要注意我们存储到List 的 val 值应该是我们出的栈顶的数据 top 的 val 值。
我们的代码流程和上面的题是差不多的，我们只需要改变 List 的存储顺序就可以了。
我们来看看代码如何编写：
▶ 代码：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new LinkedList<>();
if (root == null) {
return ret;
}
Stack<TreeNode> 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 List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new LinkedList<>();
if (root == null) {
return ret;
}
Stack<TreeNode> 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 List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new LinkedList<>();
if (root == null) {
return ret;
}
Stack<TreeNode> 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，我们的这个关于我们的二叉树的习题三但这里就结束了，同时到这里呢，我们的
数据结构 ——二叉树 也就结束了，之后呢我们进入到新的章节了，欲知后事如何，且听下回分说
拜拜啦~~~我们下篇博客再见。
原文地址：https://blog.csdn.net/2303_80388948/article/details/142302949
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！