前序遍历 加 中序遍历
求二叉树的样子。
树中
最重要的是在数组中找到左子树的下标范围和右子树的下标范围
我们需要在中序数组中，去找到根节点的下标
为了提高效率，我们可以把中序序列放进一个hash表里这样好找。查找效率很高。
/**
* Definition for a binary tree node.
* public 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;
* }
* }
*/
class Solution {
private HashMap<Integer,Integer> getindex = new HashMap<>();
//用来存储中序遍历中的根节点位置
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
//构造hash映射
for(int i = 0;i < n;i++){
getindex.put(inorder[i],i);//用值找下标
}
return MyBuildTree(preorder,0,n - 1,inorder,0,n - 1);
}
public TreeNode MyBuildTree(int[] preorder,int preLeft,int preRight,int[] inorder,int inordLeft,int inordeRight){
if(preLeft > preRight){
return null;//左右下标相等时候结束
}
//往往通过两棵树才能每次确定好应该传递的左右子树
//先建立根节点，每颗子树都要去建立根节点
TreeNode root = new TreeNode(preorder[preLeft]);
//建立根节点之后根据递归可以得到自己的左子树
//pre的左子树范围是
//preLeft + 1到 index - inordLeft + preleft
//右子树范围是
//index - inordLeft + preleft + 1,preRight
//inorder左子树范围是 inordleft,index - 1
//右子树范围是 index + 1 ,inordRight
int index = getindex.get(preorder[preLeft]);//从hash里拿到中序遍历的根节点
//根据前序遍历的最左边的那个
//这里是建立左子树，所以传递Pre和inorder的左子树
root.left = MyBuildTree(preorder, preLeft + 1, index - inordLeft + preLeft, inorder, inordLeft, index - 1);
//建立右子树，将两个右子树传递进去
root.right = MyBuildTree(preorder,index - inordLeft + preLeft + 1,preRight,inorder,index + 1,inordeRight);
return root;//每次建立完成都将根节点返回
}
}
递归终止条件就是左下标小于右下标时候
相等的时候都需要循环。
每次都是向左递归建立左子树，
这时候将每个数组左子树都交给递归，建立之后返回根节点就行了
记住返回根节点就好
你每次递归的任务都是建立一个左子树和一个右子树，左子树和右子树交给别人去做，自己只负责建立根节点。
二叉树遍历：
深度优先，广度优先
二叉树深度优先遍历
当然你必须要写个循环，将所有没被访问过的节点都丢进去进行深度优先遍历
void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
dfs(root.right);
}
二叉树广度优先遍历
void bfs(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll(); // Java 的 pop 写作 poll()
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
使用队列结构进行广度优先遍历。
但是广度优先遍历用作
层次遍历有个缺点。
就是你还没解决当前层的时候，
队列里同时会把下一层的也在进队。也就是输出时候当前队列里不仅有这层东西，还有别的层东西，所以我们最好清空整个队列，整个队列中当前层都被清空之后，再让别的层的东西输出。
加一for循环将当前前队列里已经有的节点都结束后再搞定别的节点
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) {
return ret;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<Integer>();
int currentLevelSize = queue.size();
for (int i = 1; i <= currentLevelSize; ++i) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
ret.add(level);
}
return ret;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
所以最终层序遍历的结果就是
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new ArrayDeque<>();
if (root != null) {
queue.add(root);
}
while (!queue.isEmpty()) {
int n = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < n; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(level);
}
return res;
}
这种就是，很简单真的
层序遍历每层都是左到右，存进一个list里面
这个它希望是一次左到右一次右到左
那我们还是层序遍历的玩法
只不过加一个标志位，标志这一行是左到右还是右到左
然后用一个linkedlIst
如果左到右，那么我们就是和层序遍历一样处理
Linkedlist.add()处理
如果右到左遍历，那不就是linkedlist.addfirst(加到头部就行。
二叉树深度题目
其实很简单，用递归就行了，每次进去时候
两个参数，一个是当前深度depth，另外一个是最大深度max
我们最终需要输出和返回的是最大深度Max
我们每次进去递归，都要清楚地记录当前深度和最大深度进行比较，看看谁比较大，如果有更大深度就更新更大深度，
然后进行左右递归，左右递归回来看看能不能更新最大深度，如果能更新，那么就更新最大深度后返回，如果不能更新，那么就返回当前的最大深度，我们永远返回的是最大深度
一进去的时候，也是包含了深度的，递归一开始treeNode也是有深度的，所以一开始深度为1.
这是第一个方法
我们还有第二个方法就是
层序遍历，就是bfs这个套路
用for去控制每一层节点都排除队列，然后将所有节点下一层放进来，每次层数加深我们就depth++一直到最后。
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
//直接递归统计深度
int depth = 1;
int maxDepth = 0;
maxDepth = dfs(root,depth,maxDepth);
return maxDepth;
}
public static int dfs(TreeNode root,int depth,int maxDepth){
//深度优先遍历
if(root == null){
maxDepth = Math.max(depth,maxDepth);
return maxDepth;
}
maxDepth = Math.max(depth,maxDepth);//时刻更新最大深度
int leftDepth = maxDepth,rightDepth = maxDepth;
if(root.left != null){
leftDepth = dfs(root.left,depth + 1,maxDepth);
}
if(root.right != null){
rightDepth = dfs(root.right,depth + 1,maxDepth);
}
maxDepth = Math.max(leftDepth,rightDepth);//对比一下左右两边拿个最深
return maxDepth;
}
}
求深度题目，不知道返回什么那么我们就设置一个全局变量好了
我需要知道我这个点左右子树最大深度是多少
left = dfs
right = dfs就行
dfs要返给我子树的最大深度
需要left 和right比价之后加1返回给我，因为路径 + 1嘛
那么我们可以倒着来
最后一个节点7，它的往下最大深度就是0
距离上面返回 + 1就是 1
11的最大深度就是1和 1进行比较11的最大深度就是1
4到底的最大深度就是2和 1进行比较
网上返回一个3给5
上层因此知道了自己层数
相当于最底层部门距离上层级别数
最底层部门到最底差0级，我就是最底层部门
领导想知道自己和最底层部门之间差多少级别，让底下人往上汇报
最底级别部门，距离底层差0级别，自己就是0级，汇报给更高一层部门层级就加1，更高一层部门距离最底层1级
更高部门继续往上汇报，在自己左右底层基础上对比，找到最底层是多少，然后汇报上去，继续加一层
递归往下找
当遇到我们找到了的时候
将这个节点root往上交交给上一层
告诉上一层我们找到了一个
如果一直到底层都没找到，只能告诉上一层，对不起，老大一个都没找到，返回的就是Null
红色的每一层返回的都是Null给上一层
就是这张著名的图
如果没一直到底，都没遇到要找到，那么就返回Null告诉上面自己一无所获得，只获得一个也可以，只要获得了一个就可以返回交差了。
每一个节点都要做的事情是，看看自己是不是Null或者pq?如果是，把自己交上去了
如果不是，那么你会得到左边一个部下的汇报，还有右边一个部下的汇报
最好的情况，左右都不为Null，说明你赚大发了，你就是第一人，你作为某个人的部下，把自己的大名报上去了就行，你一个人解决了所有问题
第二好的情况，你左右有一个人不为Null，说明找到了一个，那么你就把这个一个人交上去就行了
最差情况，左右为Null，一无所有，那么就把null交上去就行了。
两个指针同时往左或者往右走，
当遇到一个节点weiNull时候
直接返回另外一个节点就行了，因为另外一个节点下面挂着的节点会跟着一起走的。