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) {//入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 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，我们的这个关于我们的二叉树的习题三但这里就结束了，同时到这里呢，我们的

数据结构 ——二叉树 也就结束了，之后呢我们进入到新的章节了，欲知后事如何，且听下回分说

拜拜啦~~~我们下篇博客再见。