目录
1.二叉树结构
一个父结点，至多可以连接左右两个子节点
Java构造树结构——其实是 自定义树结点类型
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(){}
TreeNode(int val){
this.val = val;
}
TreeNode(int val,TreeNode lefTreeNode,TreeNode righTreeNode){
this.val = val;
left = lefTreeNode;
right = righTreeNode;
}
}2.广度优先搜索二叉树（迭代算法）
原理 ：（1）从上到下分层
（2）每层从左往右
解答：
（1）队列（先进先出）来迭代一层内的结点——更新队列，加入存在的左右子结点
（2）直到下一层无结点，循环再停止——该层队列为空
（3）每一层是检索 上一层更新的队列，但队列可能会在本层有新增结点——检索前先记录上一层队列数量，按此数量，一个个弹出队头并检索。
以下是示范代码：
public List<List<Integer>> levelOrder(TreeNode root) {
ArrayDeque<TreeNode> deque = new ArrayDeque<TreeNode>();
List<List<Integer>> compeleteList = new ArrayList<>();
if (root == null) {
return compeleteList;
}
deque.offer(root);
while (!deque.isEmpty()) {
List<Integer> arrList = new ArrayList<>();
int dSize = deque.size();
for(int i=0;i<dSize;++i ){
TreeNode node = deque.poll();
if (node.left != null) {
deque.offer(node.left);
}
if (node.right != null) {
deque.offer(node.right);
}
arrList.add(node.val);
}
compeleteList.add(arrList);
}
return compeleteList;
}3.深度优先搜索二叉树（递归算法）
设计思路：
（1）哪里进入下一层
（2）给上一层返回什么
（3）最底层终止条件
实例1：前序遍历
以树中间某一点 作为当前点 思考
（1）不断进入下一层，将左右子节点分别传入，作为下一层根结点
（2）若递归函数有返回值，考虑接收到本层变量，经处理返回上一层
（3）最后一层终止return 一般0，Null或者啥都无，按返回类型决定
ArrayList<Integer> list = new ArrayList<>();
public void preorder(TreeNode root){
if (root == null) {
return;
}
list.add(root.val);
preorder(root.left);
preorder(root.right);
}实例2：检测二叉树对称性
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return dfs(root.left, root.right);
}
boolean dfs(TreeNode left,TreeNode right){
if (left==null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
return dfs(left.left, right.right) && dfs(right.left, left.right);
}