树的非递归遍历

用户11369558

发布于 2024-11-20 15:07:01

7080

文章被收录于专栏：JavaJava

前序遍历

解法1：

图画的有点难看说一下大概思路 1.借助一个栈把root扔进栈中 2.此时栈中有一个root元素一直判断栈为空即可 3.其次栈内先放右树元素 再放左边元素 因为栈是先进后出原理 4.如果不为空直接出栈并用list接收

    public List<Integer> preorderTraversal(TreeNode root) {
         List<Integer> list = new ArrayList<>();
         Stack<TreeNode> stack = new Stack<>();
         if(root == null) {
            return list;
         }
         stack.push(root);
         while(!stack.isEmpty()) {
            TreeNode top = stack.pop();
            list.add(top.val);
            if(top.right != null) {
                stack.push(top.right);
            }
            if(top.left != null) {
                stack.push(top.left);
            }
         }
         return list;
    }

解法2：

 public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return list;
        }
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }

思路： 1.先看内部循环 先让cur走完左子树并且加入到list中 2.左子树走完走右子树弹出顶部元素并且访问它的右子树 3.外层循环当走完右树可能cur判空但是栈不为空所有得加上判空不然栈内没出完

中序遍历

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return list;
        }
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);
            cur = top.right;
        }
        return list;
    }

跟前序遍历解法二类似 它是左子树遍历完去右子树遍历时候打印即可

后序遍历

在前序遍历解法一的基础上只需略微修改即可便可得到后序遍历前序遍历是根左右代码写成根右左实现了前序遍历再实现一下根右左后序遍历是 左右根 根右左翻转便可得到左右根

 public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
         Stack<TreeNode> stack = new Stack<>();
         if(root == null) {
            return list;
         }
         stack.push(root);
         while(!stack.isEmpty()) {
            TreeNode top = stack.pop();
            list.add(top.val);
            if(top.left != null) {
                stack.push(top.left);
            }
            if(top.right != null) {
                stack.push(top.right);
            }
         }
         Collections.reverse(list);
         return list;
    }

解法二：

   public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return list;
        }
        TreeNode cur = root;
         TreeNode prev = null;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || top.right == prev  ) {
                list.add(top.val);
                stack.pop();
                prev = top;
            }else {
                cur = top.right;
            } 
        }
        return list;
    }

遍历到最左边时候应该判断右边是否为空如果不是空直接让它去右树上 重点：如果是空的情况下可以直接出栈并且打印同时一定得记录这次打印的位置（prev） if (top.right == null || top.right == prev)这一行检查栈顶节点top的右子树：

如果右子树为空，说明没有右子树，因此可以直接访问top并将其值加入list。
如果右子树已经被访问（即top.right == prev），这表示已经完成了对右子树的遍历，也可以访问top

可以尝试画图理解不懂可以私信我

层序遍历

  public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null) {
            return ret;
        }
        queue.offer(root);
        while(!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            while(size != 0) {
                TreeNode top = queue.poll();
                list.add(top.val);
                if(top.left != null) {
                    queue.offer(top.left);
                }
                if(top.right != null) {
                    queue.offer(top.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }