LeetCode（Stack)94. Binary Tree Inorder Traversal

电玩女神 2023-09-25 21:33 102阅读 0赞

# 1.问题 #

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Example 1:  
![在这里插入图片描述][9ac7937fc59194630afb80c683c54adf.jpeg_pic_center]

> Input: root = \[1,null,2,3\]  
> Output: \[1,3,2\]

Example 2:

> Input: root = \[\]  
> Output: \[\]

Example 3:

> Input: root = \[1\]  
> Output: \[1\]

Constraints:

*  The number of nodes in the tree is in the range \[0, 100\].
 *  \-100 <= Node.val <= 100

`Follow up: Recursive solution is trivial, could you do it iteratively?`

# 2. 解题思路 #

## 方法1： ##

> 中序遍历的顺序是左 -> 根 -> 右，可以使用递归或者迭代的方式来遍历二叉树  
> `递归`  
> 使用递归的方法实现中序遍历很简单，只需要遍历当前节点的左子树，然后访问当前节点，最后遍历当前节点的右子树即可。  
> 1.首先定义了一个全局的List类型的变量list，用来存储遍历结果。  
> 2.在inorderTraversal方法中，先判断根节点是否为空，若为空则返回list。  
> 3.若根节点不为空，就递归遍历左子树，将结果加入到list中。  
> 4.然后将根节点的值加入到list中。  
> 5.最后递归遍历右子树，将结果加入到list中。  
> 6.最后返回list即可。

## 方法2： ##

> `迭代`  
> 使用迭代的方法实现中序遍历需要用到栈的数据结构。  
> 1.首先将根节点压入栈中，然后将根节点的左子树中的节点全部压入栈中，这里需要注意的是在遍历节点时需要不断将左节点压入栈中直到最左边的叶子节点。  
> 2.接下来弹出栈顶元素，将弹出元素的值存入结果数组中，  
> 3.然后遍历当前节点的右子树，将右子树压入栈中，重复上述操作，直到栈为空为止。

# 3. 代码 #

## 代码1： ##

## 代码2： ##

class Solution {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> res = new LinkedList<Integer>(); // 用来保存遍历结果的链表
            if (root == null) return res; // 如果根节点为空，直接返回空链表
            
            Stack<TreeNode> stack = new Stack<TreeNode>(); // 辅助遍历的栈
            TreeNode cur = root; // 当前节点初始值为根节点
            while (cur != null || !stack.isEmpty()) {
         // 当前节点不为空或栈不为空时
                while (cur != null) {
         // 遍历当前节点的左子树，直到到达最左边的叶子节点
                    stack.push(cur); // 将当前节点入栈
                    cur = cur.left; // 当前节点向左移动
                }		 
                cur = stack.pop(); // 回溯到上一层节点cur
                res.add(cur.val);  // 将节点cur的值添加到结果链表中
                cur = cur.right;   // 将当前节点移动到节点A的右子树上
            }
            return res; // 返回结果链表
        }
    }

> 解题思路基本相同

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            // 用来存储结果的列表
            List<Integer> list = new ArrayList<Integer>();
            // 特判，若根节点为null，则直接返回结果列表
            if(root==null) return list;
            // 定义一个栈用于辅助遍历，初始时先将根节点压入栈中
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while(!stack.isEmpty()|| root !=null){
        
                // 不断将左子节点压入栈中，直到叶子节点
                if(root != null){
        
        			stack.push(root);
        			root = root.left;
        		}
        		else{
        
                    // 若当前节点为null，则从栈中弹出最近的父节点
        			TreeNode a = stack.pop();
        			// 将弹出节点的值加入结果列表
        			list.add(a.val);       
                    // 将当前节点指向父节点的右子节点
        			root = a.right;
                }
            }
            // 返回结果列表
            return list;
        }
    }

class Solution {
        
    	public List<Integer> inorderTraversal(TreeNode root) {
        
    	    List<Integer> res = new ArrayList<>();
    	    // method 2: iteration
    	    Stack<TreeNode> stack = new Stack<>();
    	    TreeNode cur = root;
    	    // 当前节点不为空或栈不为空时，进行遍历
    	    while (cur != null || !stack.isEmpty()) {
        
    	        while (cur != null) {
        
    	            stack.push(cur); // 将当前节点入栈
    	            cur = cur.left; // 遍历左子树
    	        }
    	        cur = stack.pop(); // 弹出栈顶元素，即最后一个左节点
    	        res.add(cur.val); // 将该节点的值加入结果集
    	        cur = cur.right; // 遍历右子树
    	    }
    	    return res;        
    	}
    }

[9ac7937fc59194630afb80c683c54adf.jpeg_pic_center]: https://img-blog.csdnimg.cn/img_convert/9ac7937fc59194630afb80c683c54adf.jpeg#pic_center