宁夏建设工程招标投标信息管理中心网站baidu百度

题目

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

解题思路

1. 中序遍历的顺序为左中右；
2. 通过递归来遍历左子树、添加数据、遍历右子树；

代码展示

package zero.zero.nine;import java.util.ArrayList;
import java.util.List;/*** 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。*/
public class Four {public static void main(String[] args) {Four four = new Four();TreeNode root = new TreeNode(1,null,new TreeNode(2,new TreeNode(3), null));System.out.println(four.inorderTraversal(root));System.out.println(four.inorderTraversal(null));System.out.println(four.inorderTraversal(new TreeNode(1)));}public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();traversal(root, ans);return ans;}public void traversal(TreeNode root, List<Integer> data){if(root == null){return;}//中序遍历结果为左中右//递归遍历左子树if(root.left != null){traversal(root.left, data);}data.add(root.val);//递归遍历右子树if(root.right != null){traversal(root.right, data);}}
}
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;}
}