Leetcode刷题100天—94. 二叉树的中序遍历(二叉树)—day08

￡神魔★判官ぃ 2022-09-09 14:53 115阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210902103746272][]

#### [94. 二叉树的中序遍历][94.] ####

难度简单1081收藏分享切换为英文接收动态反馈

给定一个二叉树的根节点 `root` ，返回它的 **中序** 遍历。

**示例 1：**

\_102\_二叉树的层序遍历.md ![img][]

输入：root = [1,null,2,3]
    输出：[1,3,2]

**示例 2：**

输入：root = []
    输出：[]

**示例 3：**

输入：root = [1]
    输出：[1]

**示例 4：**

![img][img 1]

输入：root = [1,2]
    输出：[2,1]

**示例 5：**

![img][img 2]

输入：root = [1,null,2]
    输出：[1,2]

**提示：**

*  树中节点数目在范围 `[0, 100]` 内
 *  `-100 <= Node.val <= 100`

**进阶:** 递归算法很简单，你可以通过迭代算法完成吗？

package 二叉树;
    
    import java.util.List;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.LinkedList;
    
    
    /* * 3 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/ */
    public class _94_二叉树的中序遍历 { 
    	 public List<Integer> inorderTraversal(TreeNode root) { 
    // 递归+中序
    		 List<Integer> res=new ArrayList<Integer>();
    		 
    		 preorder(root, res);
    		 return res;
    	 }
    	 public void preorder(TreeNode root,List<Integer> res) { 
    // 中序：中序遍历左子树，根节点，中序遍历右子树
    // 这里相当于阻止在递归下去
    		 if (root==null) { 
    			 return;
    		 }
    // 先遍历左子树
    		 preorder(root.left, res);
    // 将值存入res
    		 res.add(root.val);
    // 在遍历右子树
    		 preorder(root.right, res);
    		 
    	 }
    	 
    	 
    // 迭代
    	 public List<Integer> inorderTraversal2(TreeNode root) { 
    // 迭代+中序
    		 List<Integer> res=new ArrayList<Integer>();
    // 如果链表为空就直接返回空值
    		 if(root==null) { 
    			 return res;
    		 }
    // 设置一个栈
    		 Deque<TreeNode> stack=new LinkedList<TreeNode>();
    // 设置指针,指向根节点
    		 TreeNode node=root;
    // 指针不为空或栈不为空就一直循环
    		 while(node!=null ||!stack.isEmpty()) { 
    // 先遍历左节点，将其依次入栈
    			 while(node!=null) { 
    				 stack.push(node);
    				 node=node.left;
    			 }
    // 弹出栈顶元素
    			 node=stack.pop();
    // 存入列表中
    			 res.add(node.val);
    // 指针指向右子树,如果右子树为空就在弹出元素
    			 node=node.right;			 
    		 }
    // 最后输出
    		 return res;
    		 
    		 
    	 }
    
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210902103746272]: /images/20220829/bf08b6e84cb742fda0e6f2a29272056c.png
[94.]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
[img]: /images/20220829/8d0c485448044ea4848171dba93af438.png
[img 1]: /images/20220829/f8f810eca250455d897d89d768c5e9ed.png
[img 2]: /images/20220829/2f49a1096881411da4936a1a654a034c.png