【Java数据结构 -- 二叉树有关面试OJ题2】

1. 对称二叉树

思路：

1. 在根的值一样接着往下判断
2. 判断左树的左子树的值和右树的右子树的值是否相同
3. 判断左树的右子树的值和右树的左子树的值是否相同

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        return isSymmetricChild(root.left,root.right);
    }

    private boolean isSymmetricChild(TreeNode leftTree,
                                     TreeNode rightTree){
        if (leftTree == null && rightTree == null) {
            return true;
        }
        if ((leftTree == null && rightTree != null) || (leftTree != null && rightTree == null)) {
            return false;
        }
        if (leftTree.val != rightTree.val) {
            return false;
        }

        return isSymmetricChild(leftTree.left, rightTree.right) &&
                isSymmetricChild(leftTree.right , rightTree.left);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.二叉树的构建及遍历

要求：编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

import java.util.Scanner;
class TreeNode {
    public char val;
    public TreeNode left;
    public TreeNode right;


    public TreeNode(char val) {
        this.val = val;
    }
}

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static int i = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String str = in.nextLine();

            TreeNode root = createTree(str);

            inorder(root);
        }
    }
    public static TreeNode createTree(String str) {
        //1.遍历字符串str
        
        TreeNode root = null;
        if(str.charAt(i) != '#') {
            //2.根据前序遍历创建二叉树
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
            
        }else {
            i++;
        }
        //3.返回根节点
        return root;
    }

    public static void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

3.二叉树的层序遍历

层序遍历：按照从上到下，从左到右的顺序来访问每一层的节点。
思路：**利用队列的先进先出的思想，先从根节点出发，将其压入队列中，接着判断从队列中弹出来的节点的左右孩子；若该节点的左孩子不为null时，将其压入队列。一直循环，当队列为空时，说明已经把该树遍历完了。

/**
 * 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;
 *     }
 * }
 */

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            // 层序遍历
            while (size != 0){
                TreeNode cur = queue.poll();
                //System.out.print(cur.val+" ");
                tmp.add(cur.val);
                size--;
                if (cur.left != null){
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(tmp);
        }
        return ret;
    }
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

    void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            // 层序遍历
            TreeNode cur = queue.poll();
            System.out.print(cur.val+" ");
            if (cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }

        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

思路：root还是在遍历这棵树，遇到p或者q就返回

1. 如果root节点是p或者是q 那么root是最近祖先
2. 如果pq分布在root的左右两侧，那么root就是最近祖先
3. pq在root的同一侧 遇到的第一个就是公共祖先，即左边不为空，右部为空 或者左空，右不空

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return null;
        }
        if (root == p || root == q){
            return root;
        }
        // 递归左树或者右树
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if (leftTree != null && rightTree != null) {
            return root;
        }else if (leftTree != null) {
            return leftTree;
        }else {
            return rightTree;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5. 二叉树创建字符串

思路：

1. 根节点直接拼接
2. 左边为空 && 右空 直接返回
3. 左边不为空，右边为空，加“（”
4. 左边为空，右边不为空 直接加一对括号“（）”

    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }
    private void tree2strChild(TreeNode t, StringBuilder stringBuilder){
        if (t == null) {
            return;
        }
        stringBuilder.append(t.val);
        if (t.left != null) {
            stringBuilder.append("(");
            tree2strChild(t.left,stringBuilder);
            stringBuilder.append(")");
        }else {
            if (t.right == null) {
                return;
            }else {
                stringBuilder.append("()");
            }
        }
        // 判断右树
        if (t.right != null) {
            stringBuilder.append("(");
            tree2strChild(t.right,stringBuilder);
            stringBuilder.append(")");
        }else {
            return;
        }
    }
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

用栈来存放路径上的节点

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {

        if(root == null) return null;

        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();

        getPath(root,p,stackP);
        getPath(root,q,stackQ);

        int sizeP = stackP.size();
        int sizeQ = stackQ.size();

        if(sizeP > sizeQ) {
            int size = sizeP - sizeQ;
            while(size != 0) {
                stackP.pop();
                size--;
            }

        }else {
            int size = sizeQ - sizeP;
            while(size != 0) {
                stackQ.pop();
                size--;
            }
        }
        //两个栈当中的元素是一样多
        while(!stackP.isEmpty() && !stackQ.isEmpty()) {
            if(stackP.peek() == stackQ.peek()) {
                return stackP.peek();
            }else{
                stackP.pop();
                stackQ.pop();
            }
        }

        return null;
    }

    //判断左树没有这个节点 右树没有这个节点 那么当前的root就不是路径上的节点
    private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack) {
        if(root == null || node == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean flg = getPath(root.left,node,stack);
        if(flg) {
            return true;
        }
        boolean flg2 = getPath(root.right,node,stack);
        if(flg2) {
            return true;
        }

        stack.pop();

        return false;
    }
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
53
54
55
56
57
58
59
60
61
62