Subuprogrammer的博客

一、给定一个二叉树，找到该树中两个指定节点的最近公共祖先 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。 如上图，D和E的最近公共祖先就是B，G和F的最近公共祖先就是E，（一个节点也可以是自己的祖先） //这个变量是最近公共节点 private TreeNode Lac = null; //判断公共祖先 public TreeNode low

一、层序遍历 //层序遍历 public static void levelOrder(Node root){ if(root==null){ return; } //用队列来模拟 Queue<Node> queue=new LinkedList<>(); //先把根节点入队列 queue.of

一、怎样是两棵树相同 值相同，树的结构相同 二、递归实现 //检查两棵树是否相同 //值相同、树的结构相同 public static boolean isSameTree(Node p,Node q){ if(p==null&&q==null){ return true; } if(p==null||q==null){ return false; }

以下是关于二叉树的基本操作（递归实现） 1、求二叉树的总节点个数 2、求叶子节点个数 3、求第K层节点个数 4、求二叉树的高度 5、查找给定val所在的节点 //求树的节点个数 public static int sumNode(Node root) { if (root == null) { return 0; } return 1 + sumNode(root.left) + sumNode(root.right);

一、概念 二叉树：树的度为2（树中每个节点最多有两个度），树的度就是树中最大节点度。 遍历：把每个数据访问（visit)一遍，访问：打印、比较、修改，可以是各种复杂计算或者创建/删除节点。 二、遍历 1、先序遍历：先访问根节点、再访问左子树、再访问右子树 2、中序遍历：先访问左子树、再访问根节点、再访问右子树 3、后序遍历：先访问左子树、再访问右子树、再访问左子树 4、层序遍历：一层一层的进行访问...

一、概念 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。 如果两个树是空树的话，那么认为是子树。 二、举例 返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。 返回false 三、代码（递归实现） //两个二叉树是否相等：值相等并且树的结构相同 ...

一、概念 给定一个二叉树，检查它是否是镜像对称的。 对称二叉树特点：根节点为第一层，从第二层开始：节点值相同，左子树的left右子树的right，右子树的left左子树的right. 二、举例 三、代码实现 //对称二叉树:对应节点的值相同&&左右子树要刚好相反 //和根节点没有关系，看左右子树是否对称:值相等&&左子树.left和右子树.right是否对...

一、平衡二叉树 对于树中的任何一个节点，它的左子树和右子树的高度差不超过1 那么，这里就有两个方面考虑： 1、怎样求子树的高度 2、如何判断是否平衡？ 这里，使用递归来实现 public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }*/ public cl