LeetCode 94.二叉树的中序遍历

LeetCode 94

首先我们需要了解什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，即左中右。

但题目中其实是一个不太规则的非常常见的二叉树，如果补齐其中的节点就会舒服很多。

这样是不是舒服多了？

①在原图的1即为根节点，只不过此节点没有左节点，根据左中右的原则，第一个应该是1

判断当前节点是否为null，为null直接返回

②然后右节点为2，再判断2是否有左节点

③2的左节点为3，在判断3是否有左节点，为null则添加进结果集，

再回到第②步判断2是否有右节点，发现为null则把2添加进结果集。

整个遍历结束。结果为：8471329

代码部分

import java.util.ArrayList;
import java.util.List;

/**
 * @author zkkstart
 * @create 2022-03-27 10:54
 */
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> result = new ArrayList<>();
        helper(root,result);
        return result;
    }

    private void helper(TreeNode root, List<Integer> result) {
        if(root == null) return;
        helper(root.left,result);
        result.add(root.val);
        helper(root.right,result);
    }
}