二叉树oj ----＞先序 or 前序遍历（非递归实现）

「爱情、让人受尽委屈。」 2023-10-02 14:00 36阅读 0赞

题目内容：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16][]

解题思路：

> 在之前刚学二叉树的时候，接触的是递归，就是用递归的方法进行的先序遍历，它的时间复杂度和空间复杂度都比较高，现在用非递归的方法，首先想到的就是用循环，至于还用什么后面分析就会知道
> 
>  *  根据二叉树的先序遍历的要求 （根节点 左子树 右子树）；发现，它的关键在于如何处理左子树和右子树，如果用循环去遍历左子树，问题就在于那右子树就没办法遍历到（首先说，先遍历再后遍历，这种方法明显是不行的，举个很简单的例子，根节点的左子树一律没有右子树，当然可以，那也得保证右子树同样是没有左子树，既然，只适合于这种情况，其余的情况的都是反例，所以，不可行，于是，我们要考虑的是，在遍历左子树的同时，右子树也不能落下，因此，我们要采用一个容器，去放这个右子树，现在的难题又是选择哪个容器，再根据我们思路去考虑，左子树是一直往下走的，右子树的元素肯定是前面的在最前面或者最下面，我们遍历的条件又是左边完了，立马就要进行这个结点的右子树，所以，必须具备，后进先出的功能，所以，我们选择栈）
>  *  根据上面的描述，如果这个结点有右子树，我们就将其入栈，直到左子树遍历完成，此时，我们从栈当中取出元素就是这个结点的右子树

解题代码：

class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
    
            //若树为空树
            if(root == null){
                return list;
            }
    
            //树不为空树
            Stack<TreeNode> s = new Stack<>();
            TreeNode cur = root;
            while(!s.empty() || cur != null){
                while(cur != null){
    
                    list.add(cur.val);
                    if(cur.right != null){
                        s.push(cur.right);
                    }
    
                    cur = cur.left;
                }            
                
                if(!s.empty()){
                    cur = s.pop();
                }
            }
            return list;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/d3e57d2c2b26427ba39df397d3ca92bf.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16