满二叉树：每层都是满的

完全二叉树：特殊的满二叉树，可以有一个子节点，但最后一层必须是从左到右排列，中间不能有空隙，强调除了最后一层外，其他层都是满的

一、dfs深度搜索 

例题：求树的深度、树的中序遍历、树的直径、二叉树的最近公共祖先、二叉树中的最大路径和

dfs思想：都是基于递归，将大问题化解成子问题

1、树的深度

求一颗树的深度 - >求当前节点的深度，再将当前深度返回+1【包括本身Node对象】

// 本题，将求整颗树的深度转化为求各节点的深度，保证每次节点的深度都是最大值，
// 那么最终取得的就是最大值// 不需要去设个全局变量去保留最大值的副本 public int maxDepth(TreeNode root) {if(root == null)return 0;int r1 = maxDepth(root.left);int r2 = maxDepth(root.right);return Math.max(r1,r2)+1;}

2、二叉树的最近公共祖先

思路：从叶子节点开始，如果是目标对象所在的路径标记为1，否则标记为0，第一个能凑到2的节点就是最近公共祖先。

class Solution {
// 设置一个变量，去保存最近公共祖先TreeNode res;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 这里重载方法的返回值dfs(root,p,q);return res;}private int dfs(TreeNode root,TreeNode p,TreeNode q){if(root==null)return 0;int c = (root == q || root == p)?1:0;int r1 = dfs(root.left,p,q);int r2 = dfs(root.right,p,q);
// 这里表明当前 root 就是最近公共祖先，直接将其赋值给全局变量resif(r1+r2+c == 2) res = root;return (r1+r2+c==1) ?1 :0;}
}

另一种写法：

详见 递归方法寻找二叉树任意的两个节点的最近公共祖先 含代码展示和思路讲解_哔哩哔哩_bilibili

思想：本质同上面一样，我们这里是将子节点不满足条件（所在链路中不含有目标节点）的都标记为null，那么如果某条链路中含有目标节点 p/ q，则被标记为left / right，第一个收集齐left和right的就是最近公共祖先

  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;if(root == p || root == q) return root;TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);if(null == left && null == right) return null;else if(null == left && null != right) return right;else if(null != left && null == right) return left;return root;}

3、二叉树的直径

思想：也是将 求整颗树的直径转换为 子节点中，经过该节点的最大路径
同时，当前节点后面也将成为父亲的子节点，经过父节点的最大路径是依赖于子节点的最长链路
（子节点的左子树or右子树，通过max方法取最长的）
同时注意，最大路径的两端一定是叶子节点

class Solution {private int ans;public int diameterOfBinaryTree(TreeNode root) {dfs(root);return ans;}// 思路：// 逐个遍历每个点，计算该点拐弯，计算直径的值，并保存一份，// 同时这个点作为父亲的子节点，如果父亲有望成为拐点，需要依靠孩子的最长链路（孩子的左子树or右子树取最大值）// 递归解决...private int dfs(TreeNode root){if(root==null) return -1;// 枚举每个点，假设在该点拐弯，计算当前节点左子树和右子树的深度// 同时，直径的两端必定是叶子节点int lLen = dfs(root.left);int rLen = dfs(root.right);// 逐个遍历，求出最大值 ，记得加2，因为本身到左右子节点还有2ans = Math.max(ans,lLen+rLen+2);// 返回给父节点的值：左右链的最大值，记得加1，因为还要包含本身return Math.max(lLen,rLen)+1;}
}

4、二叉树中的最大路径和

这题思路和上题一样，通过求经过每个点的最大路径和
注意，如果val为负数的话，我们直接返回0
同时注意，在创建sum变量的时候，赋一个无穷小的数值，避免二叉树的val全是负数的特殊情况

class Solution {int sum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {dfs(root);return sum;}private int dfs(TreeNode root){// 到了叶子节点，直接返回0 （递归边界）if(root == null) return 0;// 计算出当前节点的左右子树int r1 = dfs(root.left);int r2 = dfs(root.right);// 算出当前节点的最大贡献值，即左右子树+自身// 并和当前最大值进行比较，如果小于的话 直接丢弃sum = Math.max(sum,r1+r2+root.val);// 返回的话，直接将当前节点与左右子树中较大的那个返回回去，作为父节点的一颗链// 同时注意和0进行比较，如果小于0，直接舍弃，即置为0return Math.max(Math.max(r1,r2)+root.val,0);}
}