【二叉树】——二叉树中序遍历

二叉树

二叉树中序遍历

中序遍历思路

官方理解：

首先我们需要了解什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

个人理解：

• 首先判断二叉树是否为空，如果为空，则返回空串

• 如果二叉树不为空（循环/递归）

  1. 首先访问根节点，然后访问根节点的左子节点，访问左子节点的左子节点，一直到某个节点没有左子节点，此时输出这个节点

  2. 判断该节点是否有右子节点，如果有，则进行1操作，如果没有，回到该节点的根节点

  3. 然后访问该根节点，输出该根节点

  4. 然后访问该根节点的右子节点，如果右子节点存在，则重复1，如果没有，则回到该根节点的根节点，进行1操作

图解

1. 判断该二叉树不为空
2. 访问A，访问A的左子节点B，访问B的左子节点D，访问D的左子节点G，访问G的左子节点，此时G的左子节点不存在，所以输出G
3. 找G的右子节点，G的右子节点不存在
4. 找G的根节点D，输出D
5. 再访问D的右子节点H，H的左子节点不存在，所以输出H
6. 找H的右子节点，H的右子节点不存在，所以回到D节点
7. 找D节点的根节点B，输出B
8. B节点的右子节点不存在，所以回到B
9. 找B的根节点A，输出A，找A的右子节点C
10. 找C的左子节点E，找E的左子节点，此时不存在E的左子节点，所以输出E
11. 找E的右子节点I，找I的左子节点，不存在，所以输出I
12. 找I的右子节点，不存在，所以回到E节点
13. 找E节点的根节点C，输出C
14. 找C节点的右子节点F，找F的左子节点，左子节点不存在，所以输出F
15. 找F节点的右子节点，不存在，所以回到C，此时树遍历完成

最后输出该图的中序遍历为

G	D	H	B	A	E	I	C	F

代码实现

• 思路1：使用递归方式实现

/** * 这种方法时间和空间利用率都是O(n) * * 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保存结果
        List<Integer> result = new ArrayList<Integer>();
        // 将根节点和result传入，进行中序遍历
        access(root, result);
        return result;
    }

    public void access(TreeNode root, List result){
    
        // 判断二叉树是否为空
        if(root == null){
    
            return ;
        }
        // 找左子节点
        access(root.left, result);
        // 输出根节点（这里可以把没有左右子节点的节点看作根节点输出）
        result.add(root.val);
        // 找右子节点
        access(root.right,result);
    }
}

• 思路二：循环迭代法

public List<Integer> inorderTraversal(TreeNode root){
    
        // 创建list保存结果
        List<Integer> result = new ArrayList<Integer>();

        // 创建stack栈来保存压入的顺序
        Stack<TreeNode> stack = new Stack();

        // 如果root不为空，则会继续压入栈中，如果root为空，则会从栈中弹出节点
        // 这里的root是变化的，不要一成不变的理解为整个树的根节点，他是每个子树的根节点
        while(root != null || !stack.isEmpty()){
    
            // 当当前节点不为空时，压入该节点的左子节点，直到该左子节点不存在为止
            while(root != null){
    
                stack.push(root);
                root = root.left;
            }
            // 弹出刚压入的左子节点
            root = stack.pop();
            // 将该结果输出
            result.add(root.val);
            // 考虑该节点的右子节点是否为空，如果为空，则继续弹出，如果不为空，则将右子节点视为一颗右子树，重新进行上述操作
            root = root.right;
        }

        return result;
    }