二叉树oj ----＞中序遍历（非递归）

柔情只为你懂 2023-10-02 14:02 21阅读 0赞

题目内容：
watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16

解题思路：

主要的思路和之前的先序遍历差不多，也是利用栈的特性，不同的地方也比较小

  • 首先遍历根节点的左子树，直到左子树为空时，遍历当前结点，中序遍历的顺序是（左子树 根节点 右子树），不能直接先遍历结点，所以，这次需要保存的是当前结点

解题代码：

  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> list = new ArrayList<>();
  5.         if(root == null){
  6.             return list;
  7.         }
  8.         Stack<TreeNode> s = new Stack<>();
  9.         TreeNode cur = root;
  10.         while(!s.empty() || cur != null){
  11.             //先往左子树遍历
  12.             while(cur != null){
  13.                 s.push(cur);
  14.                 cur = cur.left;
  15.             }
  17.             cur = s.pop();
  18.             list.add(cur.val);
  19.             cur = cur.right;
  20.         }
  21.         return list;
  22.     }
  23. }

发表评论

表情：
评论列表 （有 0 条评论，21人围观）

还没有评论，来说两句吧...

相关阅读