二叉树非递归遍历

迈不过友情╰ 2023-09-27 11:57 70阅读 0赞

![在这里插入图片描述][9ccac89b176d4a14b167faaf1b505294.gif_pic_center]

#### 文章目录 ####

*  一、二叉树的前序遍历
 *  二、二叉树的中序遍历
 *  三、二叉树的后序遍历
 *  四、从前序与中序遍历序列构造二叉树
 *  五、从中序与后序遍历序列构造二叉树
 *  六、根据二叉树创建字符串

## 一、二叉树的前序遍历 ##

给你二叉树的根节点 root ，返回它节点值的 前序 遍历  
![在这里插入图片描述][3712ff6c728b472a8ee7bc2accd546dc.png]  
**思路分析：**  
定义一个cur结点去遍历左子树，每遍历一个结点就将它放入栈中并且打印，直到左子树为空时。  
![在这里插入图片描述][9041d4a0f03a4c6e873661c93e2d3000.png]  
从栈中弹出一个元素top,cur指向top的右子树.直到cur为空并且栈也为空时便不在循环。  
![在这里插入图片描述][20fd431f51814fd89ffee13c489f0df6.png]

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

## 二、二叉树的中序遍历 ##

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。  
![在这里插入图片描述][397666dbf56440358e9c92fa4eba953a.png]  
**思路分析：**  
中序遍历与前序遍历思路大致相同，都是定义一个cur结点去遍历二叉树，不过中序遍历是一直将左子树放入stack中，直到左子树为空。  
![在这里插入图片描述][6c491e50bf7e475d8e0d6831418d7967.png]  
当左子树为空时，从stack中弹出一个结点，然后打印该节点，使cur指向top的右节点，直到cur为空并且栈也为空时便不在循环。  
![在这里插入图片描述][90e579210e1e4b05a4af3ddfcabfc504.png]

public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> list = new ArrayList<>();
            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.add(top.val);
                cur = top.right;
            }
            return list;
        }

## 三、二叉树的后序遍历 ##

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。  
![在这里插入图片描述][9c345c30be4b499e88bdd906b20ce1a7.png]  
**思路分析：**  
后序遍历同样的，遍历二叉树，将每一个结点放入stack中，直到左子树为空时。  
![在这里插入图片描述][0d16f063db2c4ca5be24ec9532ce677a.png]  
需要注意的是我们不是直接弹出栈，而是peek一下栈顶元素，这里我们就要分情况讨论了top的右子树是否为空，如果为空直接打印top元素，并且弹出，如果不为空那么使用cur指向top的右子树。![在这里插入图片描述][fe60be70ad654ca99ec1ad1d1c0cef79.png]  
但这样我们的程序会出现一个bug，我们使cur指向top右节点后，将cur打印弹出后。![在这里插入图片描述][19ac0e9f249d48c79f2c3fa20de9d95f.png]  
我们会发现程序又会使cur指向top右节点，这样无止的循环。  
![在这里插入图片描述][9b1adce233e14e339c6d19d6ea5485d3.png]  
所以我们定义一个pre变量，prev用来定义上一次打印的结点，如果top的的右节点与prev结点相同时将不再遍历右节点，而直接打印top结点，并且stack弹出元素。  
![在这里插入图片描述][5e903a7c95294702ab49ab0cbfbbcedd.png]

public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> list = new ArrayList<>();
            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) {
        
                    list.add(top.val);
                    stack.pop();
                    prev = top;
                }else {
        
                    cur = top.right;
                }
            }
            return list;
        }

## 四、从前序与中序遍历序列构造二叉树 ##

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。  
![在这里插入图片描述][87fe9c65a2674b9f83d7373d30ccee24.png]  
**思路分析：**  
这里我们随便给一颗二叉树分析一下  
![在这里插入图片描述][6a7aa6f52ba140a38562e1b8b530e254.png]  
我们遍历从前往后遍历先序数组，第一位就是二叉树的根节点，然后在中序遍历中找到该结点，该节点为分界线，该节点的左边的就是根节点的左子树，右边的就是右子树。  
![在这里插入图片描述][c3f8a7fb5c1b49d6ac1367248a6e2727.png]  
然后去构建根节点的左子树，遍历先序数组，然后在中序数组中找到该结点，左边的就是左子树，右边的就是右子树。  
![在这里插入图片描述][527972145eec451e99cb8ca2f3fc5a15.png]  
我们可以发现安装这个思路可以将二叉树构建出来，但是我们需要考虑一些条件，什么条件的时候，应该停止，首先中序遍历的数组的left应该小于right，还有得保证中序遍历中找到先序遍历的元素，否则返回-1下标，停止递归。  
![在这里插入图片描述][9091de4634c440f284fd92602ee173a1.png]

public int pre = 0;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
            return sortTree(preorder,inorder,0,inorder.length - 1);
        }
        public TreeNode sortTree(int[] preorder,int[] inorder,int left,int right) {
        
            //1.判断是否还有左右子树
            if(left > right) {
        
                return null;
            }
            TreeNode root = new TreeNode(preorder[pre]);
            int index = findIndex(inorder,left,right,preorder[pre]);
            if(index == -1) {
        
                return null;
            }
            pre++;
            root.left = sortTree(preorder,inorder,left,index - 1);
            root.right = sortTree(preorder,inorder,index + 1,right);
            return root;
        }
        public int findIndex(int[] inorder,int left,int right,int val) {
        
            if(left > right) {
        
                return  -1;
            }
            for (int i = left; i <= right; i++) {
        
                if(inorder[i] == val) {
        
                    return i;
                }
            }
            return -1;
        }

## 五、从中序与后序遍历序列构造二叉树 ##

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。  
![在这里插入图片描述][1acee1d891ab4022b7e2936d1714ed07.png]  
**思路分析：**  
这里我们随便给一颗二叉树分析一下  
![在这里插入图片描述][b55c27ce69d74d8d8d80b2f8acebb153.png]  
这次我们从后往前遍历后序数组，每遍历的一位都为该子树的根节点，不过我们得先遍历右子树，因为后序遍历的顺序是左子树-》右子树-》根节点，我们从后往前遍历后序数组，相当于反着来。中序遍历找到先序遍历的元素，左边的为左子树，右边的为右子树。  
![在这里插入图片描述][e8614fa2a3344807adacf009cc824f02.png]  
我们可以发现安装这个思路可以将二叉树构建出来，但是我们需要考虑一些条件，什么条件的时候，应该停止，首先中序遍历的数组的left应该小于right，还有得保证中序遍历中找到先序遍历的元素，否则返回-1下标，停止递归。  
而且我们定义后序数组遍历下标时，因为我们是从后往前遍历，所以我们应定义为数组大小-1.  
![在这里插入图片描述][23f4450ab1204e92be87d0f8cecff69d.png]

public int last = 0;
        public TreeNode buildTree(int[] inorder, int[] postorder) {
        
            last = inorder.length - 1;
            return sortTree1(postorder,inorder,0,inorder.length - 1);
        }
        public TreeNode sortTree1(int[] postorder,int[] inorder,int left,int right) {
        
            //1.判断是否还有左右子树
            if(left > right) {
        
                return null;
            }
            //找到中序遍历位置
            TreeNode root = new TreeNode(postorder[last]);
            int index = findIndex1(inorder,left,right,postorder[last]);
            if(index == -1) {
        
                return null;
            }
            last--;
            //构建左右子树
            root.right = sortTree1(postorder,inorder,index + 1,right);
            root.left = sortTree1(postorder,inorder,left,index - 1);
            return root;
        }
        public int findIndex1(int[] inorder,int left,int right,int val) {
        
            if(left > right) {
        
                return  -1;
            }
            for (int i = left; i <= right; i++) {
        
                if(inorder[i] == val) {
        
                    return i;
                }
            }
            return -1;
        }

## 六、根据二叉树创建字符串 ##

给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。  
空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。  
![在这里插入图片描述][79a5319b32574b58b853265db4aeac0a.png]

**思路分析：**  
按照题目的大意，就是先序二叉树，在有些情况下加入( 或者 ),我们来具体分析下什么情况下应该加什么。  
![在这里插入图片描述][0bb1cce4748c4330951ae55329709315.png]  
我们可以发现，根节点不用加任何括号，在遍历其他任何结点时加一个 ( 返回该节点时加一个 ），但还有一些边界条件需要判断一下。我们发现当左子树为空时，右子树不为空时，得加一个完整的括号，不然会破坏一一映射关系。  
![在这里插入图片描述][4f1316dd8cad44d9b7a1b64fe0be6f55.png]  
还有一点就是我们不断地拼接字符串，所以我们使用StringBuilder对象去拼接，然后toString,不然会创建大量String对象浪费空间。

public String tree2str(TreeNode root) {
        
            StringBuilder sb = new StringBuilder();
            treeToStr(root,sb);
            return sb.toString();
        }
        public void treeToStr(TreeNode root,StringBuilder sb) {
        
            if(root == null) {
        
                return;
            }
            sb.append(root.val);
            if(root.left != null) {
        
                sb.append("(");
                treeToStr(root.left,sb);
                sb.append(")");
            } else {
        
                if(root.right == null) {
        
                    return;
                }else {
        
                    sb.append("()");
                }
            }
            if(root.right == null) {
        
                return;
            } else {
        
                sb.append("(");
                treeToStr(root.right,sb);
                sb.append(")");
            }
        }

[9ccac89b176d4a14b167faaf1b505294.gif_pic_center]: https://img-blog.csdnimg.cn/9ccac89b176d4a14b167faaf1b505294.gif#pic_center
[3712ff6c728b472a8ee7bc2accd546dc.png]: https://img-blog.csdnimg.cn/3712ff6c728b472a8ee7bc2accd546dc.png
[9041d4a0f03a4c6e873661c93e2d3000.png]: https://img-blog.csdnimg.cn/9041d4a0f03a4c6e873661c93e2d3000.png
[20fd431f51814fd89ffee13c489f0df6.png]: https://img-blog.csdnimg.cn/20fd431f51814fd89ffee13c489f0df6.png
[397666dbf56440358e9c92fa4eba953a.png]: https://img-blog.csdnimg.cn/397666dbf56440358e9c92fa4eba953a.png
[6c491e50bf7e475d8e0d6831418d7967.png]: https://img-blog.csdnimg.cn/6c491e50bf7e475d8e0d6831418d7967.png
[90e579210e1e4b05a4af3ddfcabfc504.png]: https://img-blog.csdnimg.cn/90e579210e1e4b05a4af3ddfcabfc504.png
[9c345c30be4b499e88bdd906b20ce1a7.png]: https://img-blog.csdnimg.cn/9c345c30be4b499e88bdd906b20ce1a7.png
[0d16f063db2c4ca5be24ec9532ce677a.png]: https://img-blog.csdnimg.cn/0d16f063db2c4ca5be24ec9532ce677a.png
[fe60be70ad654ca99ec1ad1d1c0cef79.png]: https://img-blog.csdnimg.cn/fe60be70ad654ca99ec1ad1d1c0cef79.png
[19ac0e9f249d48c79f2c3fa20de9d95f.png]: https://img-blog.csdnimg.cn/19ac0e9f249d48c79f2c3fa20de9d95f.png
[9b1adce233e14e339c6d19d6ea5485d3.png]: https://img-blog.csdnimg.cn/9b1adce233e14e339c6d19d6ea5485d3.png
[5e903a7c95294702ab49ab0cbfbbcedd.png]: https://img-blog.csdnimg.cn/5e903a7c95294702ab49ab0cbfbbcedd.png
[87fe9c65a2674b9f83d7373d30ccee24.png]: https://img-blog.csdnimg.cn/87fe9c65a2674b9f83d7373d30ccee24.png
[6a7aa6f52ba140a38562e1b8b530e254.png]: https://img-blog.csdnimg.cn/6a7aa6f52ba140a38562e1b8b530e254.png
[c3f8a7fb5c1b49d6ac1367248a6e2727.png]: https://img-blog.csdnimg.cn/c3f8a7fb5c1b49d6ac1367248a6e2727.png
[527972145eec451e99cb8ca2f3fc5a15.png]: https://img-blog.csdnimg.cn/527972145eec451e99cb8ca2f3fc5a15.png
[9091de4634c440f284fd92602ee173a1.png]: https://img-blog.csdnimg.cn/9091de4634c440f284fd92602ee173a1.png
[1acee1d891ab4022b7e2936d1714ed07.png]: https://img-blog.csdnimg.cn/1acee1d891ab4022b7e2936d1714ed07.png
[b55c27ce69d74d8d8d80b2f8acebb153.png]: https://img-blog.csdnimg.cn/b55c27ce69d74d8d8d80b2f8acebb153.png
[e8614fa2a3344807adacf009cc824f02.png]: https://img-blog.csdnimg.cn/e8614fa2a3344807adacf009cc824f02.png
[23f4450ab1204e92be87d0f8cecff69d.png]: https://img-blog.csdnimg.cn/23f4450ab1204e92be87d0f8cecff69d.png
[79a5319b32574b58b853265db4aeac0a.png]: https://img-blog.csdnimg.cn/79a5319b32574b58b853265db4aeac0a.png
[0bb1cce4748c4330951ae55329709315.png]: https://img-blog.csdnimg.cn/0bb1cce4748c4330951ae55329709315.png
[4f1316dd8cad44d9b7a1b64fe0be6f55.png]: https://img-blog.csdnimg.cn/4f1316dd8cad44d9b7a1b64fe0be6f55.png