前序遍历结果
递归式
List<Integer> res = new LinkedList<>();
// 返回前序遍历结果
List<Integer> preorderTraverse(TreeNode root) {
traverse(root);
return res;
}
// 二叉树遍历函数
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序位置
res.add(root.val);
traverse(root.left);
traverse(root.right);
}
分解问题递归
// 定义:输入一棵二叉树的根节点,返回这棵树的前序遍历结果
List<Integer> preorderTraverse(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
// 前序遍历的结果,root.val 在第一个
res.add(root.val);
// 利用函数定义,后面接着左子树的前序遍历结果
res.addAll(preorderTraverse(root.left));
// 利用函数定义,最后接着右子树的前序遍历结果
res.addAll(preorderTraverse(root.right));
return res;
}
总结
这两种方法看似好像都是调用递归的方法,但是其实还是有点差异的,值得学习一下