树 - wenzhoullq/leetcode GitHub Wiki
用一个HashMap建造图
树的普通遍历比较简单，分为递归和栈，如果是手撕前/中/后序一般会需要你写栈的形式，唯一值得注意的是如果是后序非递归遍历的话，将前序的root=root.left改成root=root.right即可
后序遍历有个特点，它是自下往上的，因此它可以带着底层的信息往上
- 层次遍历
- 莫里斯遍历
- 后序遍历
left<right不断递归
TreeNode build(int left,int right){//当构造有多个的时候返回是List<TreeNode>
if(left>right) return null;
TreeNode root=new TreeNode(nums[i]);
TreeNode left=build(left,i-1);//构造左子树；
TreeNode right=build(i+1,right);//构造右子树；
root.left=left;
root.right=right;
return root;
}95. 不同的二叉搜索树 II//与普通的构造不同的是，它只给了数字，因此会有多种子树，需要双重for循环
96. 不同的二叉搜索树//从分类上应该不放在这里，但是它的思想和95相同，因此放到这里
- 中序遍历
二叉搜索树的特点是中序遍历的时候是升序的，如果出现逆序对，那么则不是搜索二叉树，如果出现多个逆序对，交换他们的位置即可
- 后序遍历
就是在寻找一棵树为二叉树的树的子树部分时候，是从底往上找的，因此使用是后序遍历，而且后序遍历的时候，与root节点的比较是左子树的最大值和右子树的最小值，并且return的是数组，因为一个返回值是不够使用的，并且在更新的时候，最小值更新为左子树的最小值，最大值为右子树的最大值
TreeNode pre=null;
dfs(TreeNode root){
if(root==null) return ;
!dfs(root.left);
if(pre!=null&&pre.val>=root.val) //出现逆序对后怎么处理
pre=root;
dfs(root.right);
}1373. 二叉搜索子树的最大键值和 需要后序遍历
- 树的深度
if(root==null) return 0;
int left=maxDepth(root.left)+1,
right=maxDepth(root.right)+1;
return Max.(left,right);- 树的判断
if(p==null&q==null) return true;
else if(p==null||q==null) return false;
else if(p.val!=q.val) return false;
return ;//根据题意- 树的调整
if(root==null) return root;
if(根节点不满足) 调整根节点
root.left = 函数(root.left);
root.right = 函数(root.right);
return root;- 树的深度
- 树的修改
- 树的判断
- LCA
逆时针旋转90°就是排序二叉树