JAVA解法
/**
* 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> res = new ArrayList<Integer>();
// 开始递归遍历
inorder(root, res);
// 返回结果集
return res;
}
/**
递归体
*/
public void inorder(TreeNode root, List<Integer> res) {
// 对应的根节点为空则直接返回
if (root == null) {
return;
}
// 遍历左子树
inorder(root.left, res);
// 把对应根节点的值加入结果集
res.add(root.val);
// 遍历右子树
inorder(root.right, res);
}
}
题解分析
这道题是二叉树的中序遍历1,就是以先遍历左子树并将对应的根节点分别加入结果集,再以相同的方式遍历右子树并把对应根节点加入结果集,使用递归思路简单清晰。
定义
- 二叉树的中序遍历
中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。若二叉树为空则结束返回。(百度百科 - 中序遍历)
leetcode原题:94. 二叉树的中序遍历
评论区