算法框架

灵魂三问:

  1. 函数是干什么的
  2. 函数的变量是什么
  3. 得到递归的结果应该做什么

可以对左子树和右子树得到的结果进行处理,根据问题选择遍历的位置

原始

1
2
3
4
5
6
7
void traverse(TreeNode root){
	//前序遍历
	traverse(root.left);
	//中序遍历
	traverse(root.right);
	//后序遍历
}

BST框架

1
2
3
4
5
6
7
8
9
10
11
void BST(TreeNode root,int target){
	if(root.val == target){
        //做什么
    }
    if(root.val < target){
       BST(root.left,target);
    }
    if(root.val > target){
        BST(root.right,target);
    }
}

完全二叉树节点个数

普通二叉树+满二叉树

层级遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void traverse(TreeNode root,int target){
    if(root == null){
        return;
    }
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while(!q.isEmpty()){
        TreeNode cur = q.poll();
        
        //中序遍历代码
        
        if(cur.left != null){
             q.offer(cur.left);
        }
       if(cur.right != null){
           q.offer(cur.right);
       }
        
    }
}