【算法】TOP101-二叉树篇(持续更新ing)

1. JZ36 二叉搜索树与双向链表

JZ36 二叉搜索树与双向链表

解题思路:
由题目可知,这是一颗二叉搜索树.二叉搜索树的特点就是他的中序遍历是有序的.所以本题我们大的框架就是要在中序遍历里完成.具体解题如下:

代码:

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        TreeNode head = pRootOfTree;
        convertChild(head);
        while(head.left != null){
            head = head.left;
        }
        return head;
    }
    public static TreeNode prev = null;
    public static void convertChild(TreeNode pCur){
        if(pCur == null){return;}
        convertChild(pCur.left);
        pCur.left = prev;
        if(prev != null){prev.right = pCur;}
        prev = pCur;
        convertChild(pCur.right);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

2. 100. 相同的树

100. 相同的树

解题思路:
要想判断两颗二叉树是否相同,那么就要从两个方面去考虑:

1. 二叉树的结构
2. 二叉树的值

本题我们采用递归的思想,则代码如下:

/**
 * 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 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //如果两棵树都为空,则相同
        if(p == null && q == null){
            return true;
        }
        //如果两颗树其中一颗为空,则不同
        if(p != null && q == null || p == null && q!= null){
            return false;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

3. 572. 另一棵树的子树

572. 另一棵树的子树

解题思路:
想要判断一棵树是不是另一颗树的子树,我们可以采用递归的思想.先判断子树是不是这棵树的左树,在判断是不是这棵树的右树.要是都不是,则这棵子树不是树的子树.则有以下代码:

/**
 * 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 {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root== null){
            return false;
        }
        if(isSameTree(root,subRoot)){return true;}
        if(isSameTree(root.left,subRoot)){return true;}
        if(isSameTree(root.right,subRoot)){return true;}
        return false;
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //如果两棵树都为空,则相同
        if(p == null && q == null){
            return true;}
        //如果两颗树其中一颗为空,则不同
        if(p != null && q == null || p == null && q!= null){
            return false;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

4. BM26 求二叉树的层序遍历

BM26 求二叉树的层序遍历

解题思路:

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        //先创建一个ListList列表用来存放
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while(!qu.isEmpty()){
            int size = qu.size();
            ArrayList<Integer> tmp = new ArrayList<>();
            while(size > 0){
                TreeNode cur = qu.poll();
                size--;
                tmp.add(cur.val);
                if(cur.left != null){
                    qu.offer(cur.left);
                }
                if(cur.right != null){
                    qu.offer(cur.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

5. BM33 二叉树的镜像

BM33 二叉树的镜像

解题思路:
本题我们采用子问题的思路.根据二叉镜像树的特点.我们可以看出来我们需要交换每一个根的左右节点.在代码中我们可以先递归左子树,然后让它的子节点交换,再递归右子树(此时代码中书写的仍然是左,因为在上述交换过程中已经交换了).代码如下:

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode root) {
        // write code here
        if(root == null){ return null;}
        Mirror(root.left);
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        Mirror(root.left);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

6. BM40 重建二叉树

BM40 重建二叉树

解题思路:根据前序遍历和中序遍历的特点,我们可以知道前序遍历的第一个字符"1"为二叉树的根.我们需要在中序遍历中找到"1"的位置,然后1的左边为左子树,"1"的右边为右子树.按照以上的思想,我们可以通过前序遍历和中序遍历构建出这棵树,如下所示:

代码具体实现如下:

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型一维数组 
     * @param vinOrder int整型一维数组 
     * @return TreeNode类
     */
    public int preIndex = 0;
    public TreeNode reConstructBinaryTree (int[] preorder, int[] inorder) {
        // write code here
        return buildTree(preorder,inorder,0,inorder.length-1);
    }
    // preorder:前序遍历数组下标
    // inbegin:中序遍历的首部
    // inend:中序遍历的结束
    private TreeNode buildTree(int[] preorder,int[] inorder,int inbegin,int inend){
        // 1.判断当前根结点是不是还有左子树或者右子树
        if(inbegin > inend){return null;}
        TreeNode root = new TreeNode(preorder[preIndex]);
        // 2.找到root在中序遍历的位置
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
        preIndex++;
        if(rootIndex == -1){return null;}
        // 构建左子树和右子树
        root.left = buildTree(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTree(preorder,inorder,rootIndex+1,inend);
        return root;
    }
    private int findIndex (int[] inorder,int inbegin,int inend,int val) {
        for(int i = inbegin;i <= inend;i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

7. 106. 从中序与后序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树

解题思路:本题的思路与上述第六题使用前序遍历和中序遍历重建二叉树的思路是类似的.但是需要注意的是后序遍历的顺序是左右根.所以创建树的顺序就是 根->右子树->左子树.我们只需要改一下代码的顺序.具体代码的实现如下：

/**
 * 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 {
    public int postIndex = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // write code here
        postIndex = postorder.length-1;
        return buildTree(postorder,inorder,0,inorder.length-1);
    }
    // postorder:后序遍历数组下标
    // inbegin:中序遍历的首部
    // inend:中序遍历的结束
    private TreeNode buildTree(int[] postorder,int[] inorder,int inbegin,int inend){
        // 1.判断当前根结点是不是还有左子树或者右子树
        if(inbegin > inend){return null;}
        TreeNode root = new TreeNode(postorder[postIndex]);
        // 2.找到root在后序遍历的位置
        int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
        postIndex--;
        if(rootIndex == -1){return null;}
        // 构建右子树和左子树
        root.right = buildTree(postorder,inorder,rootIndex+1,inend);
        root.left = buildTree(postorder,inorder,inbegin,rootIndex-1);
        return root;
    }
    private int findIndex (int[] inorder,int inbegin,int inend,int val) {
        for(int i = inbegin;i <= inend;i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

8. BM29 二叉树中和为某一值的路径(一)

BM29 二叉树中和为某一值的路径(一)

解题思路:对一颗数来说,要想找到相加为sum的路径,我们可以采用递归的思想.以上述题中例子来说,

如题所示,知道sum==2时我们就扎到了这条路径.虽然最右边的也符合,但是我们的思路是先找左树,找到了就返回.不关心右树的情况.具体实现代码如下:

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
     
     public int add = 0;
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root == null){
            return false;
        }
        if(root.left == null && root.right == null && sum-root.val == 0){return true;}
        return  hasPathSum(root.left,sum-root.val) ||
        hasPathSum(root.right,sum-root.val);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

9. BM35 判断是不是完全二叉树

BM35 判断是不是完全二叉树

解题思路:实现一个队列,里面先放入1节点,定义一个cur,用于记录弹出的队列中的元素,判断它是否为空.如果不为空将他的左右节点放进来.(即使左节点或者右节点为null也放,用来判断是否为完全二叉树)

具体实现代码如下:

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        if(root == null) {
            return true;
        }
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while (!qu.isEmpty()) {
            TreeNode cur = qu.poll();
            if(cur != null) {
                qu.offer(cur.left);
                qu.offer(cur.right);
            }else {
                break;
            }
        }
        //判断队列剩下的值 是否有 非null的数据
        while (!qu.isEmpty()) {
            TreeNode pop = qu.poll();
            if(pop != null) {
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

10. BM34 判断是不是二叉搜索树

BM34 判断是不是二叉搜索树

解题思路:
由于二叉树的特点,所以二叉树的中序遍历是有序的.因此我们可以在这个上面做文章.即二叉树的中序遍历是增序的,我们可以记录下上一次的值,然后与本次的值作比较,如果上一次的值比本次的值大,那么就不是有序的.返回false即可.主要步骤如下:

1. 先判断根结点是否为空
2. 左子树如果不是二叉搜索树返回false。
3. 判断当前节点是不是小于前置节点，更新前置节点。
4. 判断右子树是否为二叉搜索树.

具体实现代码如下:

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
     int pre = Integer.MIN_VALUE;
    public boolean isValidBST (TreeNode root) {
        // write code here
        if(root == null){ return true;}
        if(!isValidBST(root.left)) return false;
        if(root.val < pre){return false;}
        pre = root.val;
        return isValidBST(root.right);
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

11. BM37 二叉搜索树的最近公共祖先

BM37 二叉搜索树的最近公共祖先

12. BM38 在二叉树中找到两个节点的最近公共祖先

BM38 在二叉树中找到两个节点的最近公共祖先


解题思路:
思路：我们可以创建两个栈，寻找左树中根结点到4并存储路径放入第一个栈中，然后寻找右树中根结点到8的路径放入第二个栈中。然后我们弹出两个栈相差的元素个数，再写个循环看每一次弹出的元素是否相同，如果相同，则就是两个值的最近公共祖先。