【Java数据布局】二叉树相干算法

第一题：获取二叉树中结点个数

        得到二叉树结点个数，如果结点为空则返回0，然后再用递归盘算左树结点个数+根结点（1个）+右树结点个数。 

1. public int nodeSize(Node root){
2.         if (root == null)
3.             return 0;
4.         return nodeSize1(root.left)+nodeSize1(root.right)+1;
5. }

复制代码

第二题：获取叶子结点的个数

        得到叶子结点个数和结点总数的做法雷同，也是判定是否为空，如果该结点的左子树和右子树的都为空时那么该结点就是叶子结点，总的叶子结点就是左边叶子结点+右边叶子结点。

1. public int leafSize(Node root){
2.     if (root == null)
3.         return 0;
4.     if (root.left == null && root.right == null)
5.         return 1;
6.     return leafSize(root.left)+leafSize(root.right);
7. }

复制代码

第三题：获取第k层结点的个数

        原理和前面两题是一样，第一层有1个结点，第k层结点个数就是第k-1层的左子树+第k-1层右子树。

1. public int getNode(Node root, int k){
2.     if (root == null){
3.         return 0;
4.     }
5.     if (k == 1){
6.         return 1;
7.     }
8.     return getNode(root.left, k-1)+getNode(root.right, k-1);
9. }

复制代码

第四题：获取二叉树高度

        求高度须要左子树高度和右子树高度中最大的谁人就是二叉树的高度，加上根结点。

1. public int getHeight(Node root){
2.     if (root == null){
3.         return 0;
4.     }
5.     int left = getHeight(root.left);
6.     int right = getHeight(root.right);
8.     return Math.max(left,right)+1;
9. }

复制代码

第五题：二叉树中是否存在val

         判定二叉树是否存在val，须要以下几步：

• 判定是否为空
  
• 该结点是否与val雷同
  
• 判定左子树中是否存在与val雷同的结点
  
• 判定右子树中是否存在与val雷同的结点
  
• 左右子树都不存在与val雷同的结点，那就返回false
  

1. public boolean find(Node root, char val){
2.     if (root == null){
3.         return false;
4.     }
5.     if (root.val == val){
6.         return true;
7.     }
8.     boolean left = find(root.left, val);
9.     if (left == true){
10.         return true;
11.     }
12.     boolean right = find(root.right, val);
13.     if (right == true){
14.         return true;
15.     }
16.     return false;
17. }

复制代码

第六题：判定两棵树是否雷同

100. 雷同的树 - 力扣（LeetCode）
        判定两棵树是否雷同须要判定四种情况

• 两棵树都为空时
  
• 一棵为空，另一棵不为空时
  
• 两颗不为空，但是值不雷同
  
• 两棵都不为空，值又雷同时，再判定左子树和右子树是否同时符合
  

1. public boolean isSameTree(Node p, Node q) {
2.     if (q == null && p == null){
3.         return true;
4.     }
5.     if (q != null && p == null || q == null && p != null){
6.         return false;
7.     }
8.     if (q.val != p.val){
9.         return false;
10.     }
11.     return isSameTree(p.left, q.left)&& isSameTree(p.right, q.right);
12. }

复制代码

第七题：判定是否是子树

572. 另一棵树的子树 - 力扣（LeetCode）
         判定大的二叉树中是否存在一个小的二叉树，判定条件：

• 如果大的二叉树的结点为空，小的二叉树不为空，则不是子树
  
• 然后再判定两棵树是否雷同，雷同也是子树
  
• 然后再遍历左子树的每一个结点，如果左子树存在子树返回true即可
  
• 判定右子树的每个结点，存在子树则返回true
  
• 左右都不存在子树返回false 
  

1. public boolean isSubtree(Node root, Node subRoot) {
2.     if (root == null){
3.         return false;
4.     }
5.     if (isSameTree(root, subRoot)) {
6.         return true;
7.     }
8.     boolean left = isSubtree(root.left, subRoot);
9.     if (left == true){
10.         return true;
11.     }
12.     boolean right = isSubtree(root.right, subRoot);
13.     if (right == true){
14.         return true;
15.     }
16.     return false;
17. }

复制代码

第八题：反转二叉树

226. 翻转二叉树 - 力扣（LeetCode）
        反转二叉树，重要就是反转每一个结点的左右子树，如果为空就竣事，在这过程中使用了递归，末了返回根结点。

1. public Node invertTree(Node root) {
2.     if(root == null){
3.         return null;
4.     }
5.     Node temp = root.left;
6.     root.left = root.right;
7.     root.right = temp;
9.     invertTree(root.left);
10.     invertTree(root.right);
11.     return root;
12. }

复制代码

第九题：判定是否是均衡二叉树

110. 均衡二叉树 - 力扣（LeetCode）
        判定是否为均衡二叉树的重要条件是每棵子树的左右子树差值小于即是1；以是一边遍历一边比力差值。但是这个方法尚有一个限定就是复杂度高（重复盘算），可以直接在求高度是边盘算差值。

1. public boolean isBalanced(Node root) {
2.         if(root == null){
3.             return false;
4.         }
5.         int left = getHeight(root.left);
6.         int right = getHeight(root.right);
7.         if (Math.abs(left - right) > 1){
8.             return false;
9.         }
10.         boolean leftB = isBalanced(root.left);
11.         boolean rightB = isBalanced(root.right);
12.         return true;
13. }

复制代码

第十题：判定是否是对称二叉树

101. 对称二叉树 - 力扣（LeetCode）
        判定是否对称的依据是根结点左右子树的结点是否对称，如果布局满意对称还须要结点对应的值雷同（左子树的左结点须要与右子树的右结点雷同）。

1. public boolean isSymmetric(Node root) {
2.     if (root == null){
3.         return true;
4.     }
5.     return isSymmetricChild(root.left, root.right);
6. }
7. public boolean isSymmetricChild(Node p, Node q) {
8.     if (p == null && q == null){
9.         return true;
10.     }
11.     if (p == null || q == null){
12.         return false;
13.     }
14.     if (p.val != q.val){
15.         return false;
16.     }
17.     return isSymmetricChild(p.left,q.right) && isSymmetricChild(p.right, q.left);
18. }

复制代码

第十一题：分层遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）
        标题所表达的意思是将每一层的元素都举行输出；思绪是从根结点开始先辈行入队，先输出队列中的队头结点，然后每出一个元素就要将这个元素的左右结点都入队，直至队列为空。
如果须要返回一个链表，那就一次进一层（通过盘算器计入队列中一层有多少元素，然后通过循环串联链表，并将串联在链表中的结点的左右结点都入队），直至队中节点为空。

1. public void levelOrder1(Node root){
2.     if (root == null){
3.         return ;
4.     }
5.     Queue<Node> q = new LinkedList<>();
6.     q.offer(root);
7.     while (!q.isEmpty()){
8.         Node cur = q.poll();
9.         System.out.print(cur.val+"  ");
10.         if (cur.left != null){
11.             q.offer(cur.left);
12.         }
13.         if (cur.right != null){
14.             q.offer(cur.right);
15.         }
16.     }
17. }

复制代码

第十二题：迩来公共先人

236. 二叉树的迩来公共先人 - 力扣（LeetCode）
        迩来公共先人意思就是在一棵树中挑两个结点然后向根结点的方向探求两个结点迩来的交点。以是要找出两个结点全部的情况，经实验总结了三种情况：两个结点同在左边、同在右边、以及一个结点在左边一个结点在右边。思绪就是先判空再是如果有一个结点满意是根结点，那就直接返回根节点即可（在一个棵树中没有比根结点更大的先人了），然后就开始遍历，在左右两边分别遍历，探求两个结点的位置，然后就是返回迩来先人。

1. public Node lowestCommonAncestor(Node root, Node p, Node q){
2.     if (root == null){
3.         return null;
4.     }
5.     if (p == root || q == root){
6.         return root;
7.     }
8.     Node left = lowestCommonAncestor(root.left, p, q);
9.     Node right = lowestCommonAncestor(root.right, p, q);
10.     if (left != null && right != null){     //q和p一个在左一个在右
11.         return root;
12.     }else if (left != null){    //p和q都在左
13.         return left;
14.     }else{  //p和q都在右
15.         return right;
16.     }
17. }

复制代码