二叉树的理论基础
关于二叉树,你该了解这些!| 二叉树理论基础一网打尽,二叉树的种类、二叉树的存储方式、二叉树节点定义、二叉树的遍历顺序_哔哩哔哩_bilibili
二叉搜索树:二叉搜索树是一个有序树。左子树不为空,则左子树上所有节点的值均小于根节点的值;右子树不为空,则右子树上所有结点的值均大于根节点的值
二叉树的存储方式
二叉树可以用链表存储,也可以用数组存储。详细解答
二叉树的递归遍历
每次写递归都要靠直觉? 这次带你学透二叉树的递归遍历!| LeetCode:144.前序遍历,145.后序遍历,94.中序遍历_哔哩哔哩_bilibili
递归三部曲:
1、确定递归的参数和返回值
2、确定终止条件
3、确定单层递归的逻辑
以前序遍历为例:
1、递归的参数和返回值: 因为要打印出遍历后的节点的数值,需要传入TreeNode来存放节点的数值;返回类型为空
class Solution{
public List<Integer> preorderTraversal(TreeNode root){
List<Integer> result = new ArrayList<Integer>();
preorder(root,result);
return result;
}
public void preorder(TreeNode root, List<Integer> result){
}
}
2、终止条件:节点为空
if(root == null) {
return;
}
3、单层递归的逻辑:先取中间节点,然后才是左、右
result.add(root.val);
preorder(root.left,result);
preorder(root.right,result);
综合代码:
class Solution{
public List<Integer> preorderTraversal(TreeNode root){
List<Integer> result = new ArrayList<Integer>();
preorder(root,result);
return result;
}
public void preorder(TreeNode root, List<Integer> result){
if(root == null) {
return;
}
result.add(root.val);
preorder(root.left,result);
preorder(root.right,result);
}
}
中序遍历和后序遍历是一样的,不过在3、单层递归逻辑中,语句的顺序发生了改变:
中序遍历:
class Solution{
public List<Integer> inorderTraversal(TreeNode root){
List<Integer> result = new ArrayList<Integer>();
preorder(root,result);
return result;
}
public void preorder(TreeNode root, List<Integer> result){
if(root == null) {
return;
}
preorder(root.left,result);
result.add(root.val);
preorder(root.right,result);
}
}
后序遍历:
class Solution{
public List<Integer> postorderTraversal(TreeNode root){
List<Integer> result = new ArrayList<Integer>();
preorder(root,result);
return result;
}
public void preorder(TreeNode root, List<Integer> result){
if(root == null) {
return;
}
preorder(root.left,result);
preorder(root.right,result);
result.add(root.val);
}
}
标签:preorder,遍历,14,List,随想录,result,root,二叉树
From: https://blog.csdn.net/lilith_2001/article/details/136831848