算法：中序遍历二叉树94. Binary Tree Inorder Traversal

古城微笑少年丶 2022-09-17 01:00 36阅读 0赞

# [94. Binary Tree Inorder Traversal][] #

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

Example 1:

![在这里插入图片描述][651c80a0a5ff47d38a59ce1d3d951dbf.png]

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

Example 2:

Input: root = []
    Output: []

Example 3:

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

Example 4:  
![在这里插入图片描述][f95eacaf396a4bac83d98dc7224a9b06.png]

Input: root = [1,2]
    Output: [2,1]

Example 5:  
![在这里插入图片描述][48d3123efc7a4e29a59147a2e13bc5cd.png]

Input: root = [1,null,2]
    Output: [1,2]

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?

# 递归算法 #

/**
     * 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<>();
            helper(root, list);
            
            return list;
        }
        
        private void helper(TreeNode root, List<Integer> list) {
        
            if (root == null) return;
            helper(root.left, list);
            list.add(root.val);
            helper(root.right, list);
        }
    }

# 遍历解法 #

将一个 Node 的所有左子节点都压入堆栈，这样我的想法就很清楚了：

1.  我们将 root 的所有左孩子推入堆栈，直到没有更多节点。
2.  然后我们从我们调用的堆栈中弹出cur。
3.  添加cur到结果列表
4.  设置`root = node.right`， 以此循环。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5p625p6E5biI5piT562L_size_20_color_FFFFFF_t_70_g_se_x_16]

/**
     * 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<>();
            Stack<TreeNode> stack = new Stack<>();
            while (root != null || !stack.isEmpty()) {
        
                while(root != null) {
        
                    stack.add(root);
                    root = root.left;
                }
                TreeNode node = stack.pop();
                list.add(node.val);
                root = node.right;
            }
            
            return list;
        }
    }

[94. Binary Tree Inorder Traversal]: https://leetcode.com/problems/binary-tree-inorder-traversal/
[651c80a0a5ff47d38a59ce1d3d951dbf.png]: /images/20220828/d67f085d58164aecae4e9868424778bf.png
[f95eacaf396a4bac83d98dc7224a9b06.png]: /images/20220828/f9f38a6dba1d46f394e270664d35191e.png
[48d3123efc7a4e29a59147a2e13bc5cd.png]: /images/20220828/ef6d7aba0bde4a78bc4e41b522213bd1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5p625p6E5biI5piT562L_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/391ced83641d4f6fbb96c26e0acfd12d.png