二叉樹題目

印度阿三17 2019-03-21

展開全文

本文轉載自http://blog.csdn.net/fightforyourdream/article/details/16843303

?
題目：?
1. 前序、中序、后序遍歷二叉樹?
2. 層序遍歷二叉樹?
3. 獲得二叉樹的深度?
4. 獲得二叉樹的節(jié)點個數(shù)?
5. 判斷兩棵二叉樹是否為相同的二叉樹?
6. 判斷二叉樹是否為平衡二叉樹?
7. 獲得二叉樹的葉子節(jié)點個數(shù)?
8. 獲得二叉樹第K層上的節(jié)點個數(shù)?
9. 將二叉查找樹變?yōu)橛行虻碾p向鏈表?
10. 求二叉樹中兩個節(jié)點的最低公共祖先節(jié)點?
11. 求二叉樹兩個節(jié)點之間的最大距離?
12. 求從根節(jié)點出發(fā)到node的路徑path?
13. 根據(jù)兩個遍歷序列重建二叉樹?
14. 判斷二叉樹是否為完全二叉樹?
15.判斷二叉樹B是不是二叉樹A的子結構?
16.二叉樹的鏡像?
17.判斷一個序列是否是二叉搜索樹的后序遍歷序列?
18.求二叉樹中和為某一值的路徑

代碼如下：?
　　二叉樹的基本組成：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

　　測試主方法：

import java.util.*;

/**
 * 二叉樹題目匯總
 *
 * 1、前序、中序、后序遍歷二叉樹，preOrder1，preOrder2,inOrder1,inOrder2,postOrder1,postOrder2
 * 2、層序遍歷二叉樹，levelOrder1,levelOrder2
 * 3、獲得二叉樹的深度，getDepth
 * 4、獲得二叉樹的節(jié)點個數(shù)，getNodesNum
 * 5、判斷兩棵二叉樹是否為相同的二叉樹，isSameTree
 * 6、判斷二叉樹是否為平衡二叉樹，isAVL
 * 7、獲得二叉樹的葉子節(jié)點個數(shù)，getLeafNodeNum
 * 8、獲得二叉樹第K層上的節(jié)點個數(shù)，getKthLevelNodesNum
 * 9、將二叉查找樹變?yōu)橛行虻碾p向鏈表，convertBST2DLL
 * 10、求二叉樹中兩個節(jié)點的最低公共祖先節(jié)點，getLastCommonParent
 * 11、求二叉樹兩個節(jié)點之間的最大距離，getMaxDistance
 * 12、求從根節(jié)點出發(fā)到node的路徑path,getNodePath
 * 13、根據(jù)兩個遍歷序列重建二叉樹，rebuildBinaryTreeByPreAndIn,rebuildBinaryTreeByInAndPost
 * 14、判斷二叉樹是否為完全二叉樹，isCompleteBinaryTree
 */
@SuppressWarnings("All")
public class TreeDemo {
    /*
                 1
                /                2   3
              / \                4  5   6
     */
    public static void main(String[] args) {
        TreeNode r1 = new TreeNode(1);
        TreeNode r2 = new TreeNode(2);
        TreeNode r3 = new TreeNode(3);
        TreeNode r4 = new TreeNode(4);
        TreeNode r5 = new TreeNode(5);
        TreeNode r6 = new TreeNode(6);

        r1.left = r2;
        r1.right = r3;
        r2.left = r4;
        r2.right = r5;
        r3.right = r6;

//        preOrder1(r1);
//        System.out.println("前序遍歷，遞歸");
//        preOrder2(r1);
//        System.out.println("前序遍歷，迭代");
//
//        inOrder1(r1);
//        System.out.println("中序遍歷，遞歸");
//        inOrder2(r1);
//        System.out.println("中序遍歷，迭代");

//        postOrder1(r1);
//        System.out.println("后序遍歷，遞歸");
//        postOrder2(r1);
//        System.out.println("后序遍歷，迭代");

//        levelOrder1(r1);
//        System.out.println("層序遍歷，迭代");
//        levelOrder2(r1);
//        System.out.println("層序遍歷， 遞歸");

//        System.out.println(getDepth1(r1));
//        System.out.println(getDepth2(r1));

        System.out.println(getNodesNum1(r1));
        System.out.println(getNodesNum2(r1));
    }
}

1. 前序、中序、后序遍歷二叉樹

　　以下分別是前序，中序，后序遍歷二叉樹的遞歸和迭代解法，具體思路在方法前有說明。

    /**
     * 前序遍歷，遞歸解法
     * （1）如果二叉樹為空，空操作
     * （2）如果二叉樹不為空，訪問根節(jié)點，前序遍歷左子樹，前序遍歷右子樹
     */
    public static void preOrder1(TreeNode root) {
        if(root == null) {
            return;
        }
        System.out.print(root.val   " ");

        preOrder1(root.left);
        preOrder1(root.right);
    }

/**

     * 前序遍歷，迭代
     *      用一個輔助stack，總是把右孩子放進棧
     */
    public static void preOrder2(TreeNode root) {
        if(root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop(); //出棧頂元素
            System.out.print(cur.val   " ");

            // 關鍵點：要先壓入右孩子，再壓入左孩子，這樣在出棧時會先打印左孩子再打印右孩子
            if(cur.right != null) {
                stack.push(cur.right);
            }
            if(cur.left != null) {
                stack.push(cur.left);
            }
        }
    }

?

    /**
     * 中序遍歷，遞歸
     */
    public static void inOrder1(TreeNode root) {
        if(root == null) {
            return;
        }
        inOrder1(root.left);
        System.out.print(root.val   " ");
        inOrder1(root.right);
    }

?

    /**
     * 中序遍歷迭代解法 ，用棧先把根節(jié)點的所有左孩子都添加到棧內，
     * 然后輸出棧頂元素，再處理棧頂元素的右子樹
     * http://www./watch?v=50v1sJkjxoc
     *
     * 還有一種方法能不用遞歸和棧，基于線索二叉樹的方法，較麻煩以后補上
     * http://www./inorder-tree-traversal-without-recursion-and-without-stack/

     */
    public static void inOrder2(TreeNode root) {
        if(root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (true) {
            while (cur != null) {   // 先添加一個非空節(jié)點所有的左孩子到棧
                stack.push(cur);
                cur = cur.left;
            }

            if(stack.isEmpty()) {
                break;
            }

            // 因為此時已經沒有左孩子了，所以輸出棧頂元素
            cur = stack.pop();
            System.out.print(cur.val   " ");
            cur = cur.right;
        }
    }

?

    /**
     * 后序遍歷，遞歸
     */
    public static void postOrder1(TreeNode root) {
        if(root == null) {
            return;
        }

        postOrder1(root.left);
        postOrder1(root.right);
        System.out.print(root.val   " ");
    }

1
2
3
4
5
6
7
8
9
10
11
12

    /**
     * 后序遍歷，迭代
     * 　　需要用到兩個棧，分別將左子樹和右子樹壓入棧1，再取出第一個棧中的元素存放到棧2中，完成后序遍歷的逆序輸出
     * @param root
     */
    public static void postOrder2(TreeNode root) {
        if(root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> out = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            out.push(cur);
            if(cur.left != null) {
                stack.push(cur.left);
            }
            if(cur.right != null) {
                stack.push(cur.right);
            }
        }
        while (!out.isEmpty()) {
            System.out.print(out.pop().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

2. 層序遍歷二叉樹

　　分別采用迭代和遞歸的方法來分層遍歷二叉樹

    /**
     * 分層遍歷二叉樹（按層次從上往下，從左往右）迭代
     * 相當于廣度優(yōu)先搜索，使用隊列實現(xiàn)。隊列初始化，將根節(jié)點壓入隊列。當隊列不為空，進行如下操作：彈出一個節(jié)點
     */
    public static void levelOrder1(TreeNode root) {
        if(root == null) {
            return;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.removeFirst();
            System.out.print(cur.val   " ");

            if(cur.left != null) {
                queue.add(cur.left);
            }
            if(cur.right != null) {
                queue.add(cur.right);
            }
        }
    }

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

    /**
     * 層序遍歷，遞歸
     * 很少有人會用遞歸去做level traversal
     *  基本思想是用一個大的ArrayList，里面包含了每一層的ArrayList。
     *  大的ArrayList的size和level有關系
     *
     *  這是我目前見到的最好的遞歸解法！
     *  http://discuss./questions/49/binary-tree-level-order-traversal#answer-container-2543
     */
    public static void levelOrder2(TreeNode root) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        dfs(root, 0, ret);
        System.out.print(ret);
     }

    public static void dfs(TreeNode root, int level, ArrayList<ArrayList<Integer>> ret) {
        if(root == null) {
            return;
        }
        if(level >= ret.size()) {
            ret.add(new ArrayList<Integer>());
        }
        ret.get(level).add(root.val);   //把節(jié)點值加入到表示那一層的list集合中
        dfs(root.left, level 1, ret);
        dfs(root.right, level 1, 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

3.獲得二叉樹的深度

　　獲得二叉樹深度的遞歸和迭代解法：

    /**
     * 求二叉樹的深度（高度） 遞歸解法： O(n)
     * （1）如果二叉樹為空，二叉樹的深度為0
     * （2）如果二叉樹不為空，二叉樹的深度 = max(左子樹深度， 右子樹深度)   1
     */
    public static int getDepth1(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = getDepth1(root.left);
        int right = getDepth1(root.right);
        return Math.max(left, right) 1;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13

    /**
     * 求二叉樹的深度（高度） 迭代解法： O(n)
     * 基本思想同LevelOrder，還是用一個Queue
     */
    public static int getDepth2(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int depth = 0;
        int currentLevelNodes = 1;  //當前層的節(jié)點數(shù)
        int nextLevelNodes = 0; //下一層的節(jié)點數(shù)
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.removeFirst(); //從隊頭位置開始移除
            currentLevelNodes--;    //當前層數(shù)節(jié)點減1
            if(cur.left != null) {  //當前節(jié)點有左子節(jié)點，加入隊列中
                queue.add(cur.left);
                nextLevelNodes  ;   //并將下一層節(jié)點數(shù)加1
            }
            if(cur.right != null) {
                queue.add(cur.right);
                nextLevelNodes  ;
            }
            if(currentLevelNodes == 0) {    //如果處理完當前層的所有節(jié)點
                depth  ;    //深度加1
                currentLevelNodes = nextLevelNodes; //初始化當前層為下一層
                nextLevelNodes = 0;
            }
        }
        return depth;
    }

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

4.獲得二叉樹的節(jié)點個數(shù)

　　遞歸：

    /**
     * 二叉樹的節(jié)點個數(shù)，遞歸
     */
    public static int getNodesNum1(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = getNodesNum1(root.left);
        int right = getNodesNum1(root.right);
        return left   right   1;
    }

1
2
3
4
5
6
7
8
9
10
11

    /**
     * 二叉樹的節(jié)點個數(shù)，迭代
     * java用LinkedList來模擬queue的用法
     */
    public static int getNodesNum2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int count = 1;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.removeFirst();
            if(cur.left != null) {
                queue.add(cur.left);
                count  ;
            }
            if(cur.right != null) {
                queue.add(cur.right);
                count  ;
            }
        }
        return count;
    }

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

5.判斷兩棵二叉樹是否為相同的二叉樹

    /**
     * 判斷兩顆二叉樹是否為相同的二叉樹,遞歸
     */
    public static boolean isSameTree1(TreeNode r1, TreeNode r2) {
        // 如果兩棵二叉樹都為空，返回真
        if(r1 == null && r2 == null) {
            return true;
        }
        // 如果兩棵二叉樹一棵為空，另一棵不為空，返回假
        else if(r1 == null || r2 == null) {
            return false;
        }

        if(r1.val != r2.val) {
            return false;
        }

        boolean left = isSameTree1(r1.left, r2.left);    //分別比較左子樹和右子樹是否相等
        boolean right = isSameTree1(r1.right, r2.right);
        return left && right;
    }

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

    /**
     * 判斷兩顆二叉樹是否相同，迭代解法
     *    分別用兩個棧來存儲兩棵樹，采用前序遍歷的方法依次比較兩顆二叉樹的各個節(jié)點的值是否相等，
     *    如果不相等直接返回空，相等就繼續(xù)將后面的節(jié)點入棧
     */
    public static boolean isSameTree2(TreeNode r1, TreeNode r2) {
        if(r1 == null && r2 == null) {
            return true;
        }
        else if(r1 == null || r2 == null) {
            return false;
        }

        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();

        s1.add(r1);
        s2.add(r2);
        while (!s1.isEmpty() && !s2.isEmpty()) {
            TreeNode n1 = s1.pop();
            TreeNode n2 = s2.pop();
            if(n1 == null && n2 == null) {
                continue;
            }
            else if(n1!=null && n2 != null && n1.val == n2.val) {
                s1.push(n1.right);
                s1.push(n1.left);
                s2.push(n2.right);
                s2.push(n2.left);
            }
            else {
                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

6.判斷二叉樹是否為平衡二叉樹

    /**
     * 判斷二叉樹是不是平衡二叉樹 遞歸解法：
     * （1）如果二叉樹為空，返回真
     * （2）如果二叉樹不為空，如果左子樹和右子樹都是AVL樹并且左子樹和右子樹高度相差不大于1，返回真，其他返回假
     */
    public static boolean isAVL(TreeNode root) {
        if(root == null) {
            return true;
        }
        if(Math.abs(getDepth1(root.left) - getDepth1(root.right)) > 1) {
            return false;
        }
        return isAVL(root.left) && isAVL(root.right);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14

7.獲得二叉樹中葉子節(jié)點的個數(shù)

    /**
     * 求二叉樹中葉子節(jié)點的個數(shù)，遞歸
     */
    public static int getLeafNodeNum1(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeNum1(root.left)   getLeafNodeNum1(root.right);
    }

1
2
3
4
5
6
7
8
9
10
11
12

    /**
     * 求二叉樹中葉子節(jié)點的個數(shù)，迭代
     *      基于層序遍歷的思想
     */
    public static int getLeafNodeNum2(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int count = 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode cur = queue.removeFirst();
            if(cur.left == null && cur.right == null) {
                count  ;
            }
            if(cur.left != null) {
                queue.add(cur.left);
            }
            if(cur.right != null) {
                queue.add(cur.right);
            }
        }
        return count;
    }

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

8.求二叉樹第K層節(jié)點的個數(shù)

    /**
     * 求二叉樹第K層節(jié)點的個數(shù)
     * （1）如果二叉樹為空或者k<1返回0
     * （2）如果二叉樹不為空并且k==1，返回1
     * （3）如果二叉樹不為空且k>1，返回root左子樹中k-1層的節(jié)點個數(shù)與root右子樹k-1層節(jié)點個數(shù)之和
     *
     * 求以root為根的k層節(jié)點數(shù)目 等價于 求以root左孩子為根的k-1層（因為少了root那一層）節(jié)點數(shù)目 加上
     * 以root右孩子為根的k-1層（因為少了root那一層）節(jié)點數(shù)目
     *
     * 所以遇到樹，先把它拆成左子樹和右子樹，把問題降解
     */
    public static int getKthLevelNodesNum1(TreeNode root, int k) {
        if(root == null || k < 1) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }

        int left = getKthLevelNodesNum1(root.left, k-1);     //求root左子樹的k-1層節(jié)點數(shù)
        int right = getKthLevelNodesNum1(root.right, k-1);
        return left right;
    }

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

    /**
     * 求二叉樹第K層節(jié)點數(shù)目，迭代
     *    利用層序遍歷的思想
     */
    public static int getKthLevelNodesNum2(TreeNode root, int k) {
        if(root == null || k < 1) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int currentLevelNodes = 1;
        int nextLevelNodes = 0;
        int i = 1;

        while (!queue.isEmpty() && i < k) {
            TreeNode cur = queue.removeFirst(); //移除隊頭位置
            currentLevelNodes--;    //當前層節(jié)點數(shù)減1
            if(cur.left != null) {
                queue.add(cur.left);
                nextLevelNodes  ;
            }
            if(cur.right != null) {
                queue.add(cur.right);
                nextLevelNodes  ;
            }
            if(currentLevelNodes == 0) {
                currentLevelNodes = nextLevelNodes;
                nextLevelNodes = 0;
                i  ;
            }

        }
        return currentLevelNodes;
    }

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

9.將二叉查找樹變?yōu)橛行虻碾p鏈表

    /**
     * 將二叉查找樹變?yōu)橛行虻碾p向鏈表 要求不能創(chuàng)建新節(jié)點，只調整指針。
     *      節(jié)點的左即為鏈表前一節(jié)點，右即為鏈表后一節(jié)點
     * 遞歸解法：
     * 參考了http:///questions/11511898/converting-a-binary-search-tree-to-doubly-linked-list#answer-11530016
     * 感覺是最清晰的遞歸解法，但要注意遞歸完，root會在鏈表的中間位置，因此要手動
     * 把root移到鏈表頭或鏈表尾
     */
    public static TreeNode convertBST2DLL1(TreeNode root) {
        root = convertBST2DLLSub(root);

        // root會在鏈表的中間位置，因此要手動把root移到鏈表頭
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

    /**
     * 遞歸轉換二叉查找樹為雙向鏈表(DLL)
     */
    public static TreeNode convertBST2DLLSub(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) {
            return root;
        }

        TreeNode tmp = null;
        if(root.left != null) {     //處理左子樹
            tmp = convertBST2DLLSub(root.left);
            while (tmp.right != null) { //尋找最右節(jié)點
                tmp = tmp.right;
            }
            tmp.right = root;   //把左子樹處理后結果和root連接
            root.left = tmp;
        }
        if(root.right != null) {    //處理右子樹
            tmp = convertBST2DLLSub(root.right);
            while (tmp.left != null) {  //尋找最左節(jié)點
                tmp = tmp.left;
            }
            tmp.left = root;    //把右子樹處理后結果和root連接
            root.right = tmp;
        }
        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
33
34
35
36
37
38
39
40
41
42
43
44
45

    /**
     * 二叉查找樹轉換為雙向鏈表，迭代解法
     *      基本思想同中序遍歷二叉樹
     */
    public static TreeNode convertBST2DLL2(TreeNode root) {
        if(root == null) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;    //指向當前正在處理的節(jié)點
        TreeNode old = null;    //前一節(jié)點
        TreeNode head = null;   //雙向鏈表的頭結點

        while (true) {
            while (cur != null) {   //將所有左節(jié)點全部入棧
                stack.push(cur);
                cur = cur.left;
            }

            if(stack.isEmpty()) {
                break;
            }

            //由于此時沒有左孩子了，所以輸出棧頂元素
            cur = stack.pop();
            if(old != null) {
                old.right = cur;
            }
            if(head == null) {  //第一個結點為雙向鏈表頭結點
                head = cur;
            }
            old = cur;  //更新old
            cur = cur.right;    //準備處理右子樹
        }
        return head;
    }

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

10.求二叉樹中兩個節(jié)點的最低公共祖先節(jié)點

    /**
     * 求二叉樹中兩個節(jié)點的最低公共祖先節(jié)點
     * 遞歸解法：
     * （1）如果兩個節(jié)點分別在根節(jié)點的左子樹和右子樹，則返回根節(jié)點
     * （2）如果兩個節(jié)點都在左子樹，則遞歸處理左子樹；如果兩個節(jié)點都在右子樹，則遞歸處理右子樹
     */
    public static TreeNode getLastCommonParent(TreeNode root, TreeNode n1, TreeNode n2) {
        if(findNode(root.left, n1)) {    //如果節(jié)點n1在樹的左子樹
            if(findNode(root.right, n2)) {  //節(jié)點n2在樹的右子樹
                return root;
            }
            else {  //節(jié)點n2也在左子樹，則遞歸處理左子樹
                return getLastCommonParent(root.left, n1, n2);
            }
        }
        else {  //n1在右子樹
            if(findNode(root.left, n2)) {
                return root;
            }
            else {
                return getLastCommonParent(root.right, n1, n2);
            }
        }
    }

    //遞歸判斷一個節(jié)點是否在樹里
    public static boolean findNode(TreeNode root, TreeNode n) {
        if(root == null || n == null) {
            return false;
        }
        if(root == n) {
            return true;
        }
        //先嘗試在左子樹里查找
        boolean found = findNode(root.left, n);
        if(!found) {    //如果不在左子樹中
            found = findNode(root.right, n);    //在右子樹中查找
        }
        return found;
    }

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

    //求二叉樹中兩個節(jié)點的最低公共祖先節(jié)點，更加簡便的遞歸方法
    public static TreeNode getLastCommonParent1(TreeNode root, TreeNode n1, TreeNode n2) {
        if(root == null) {
            return null;
        }
        //如果兩者有一個與root 相同
        if(root.equals(n1) || root.equals(n2)) {
            return root;
        }

        TreeNode commonInLeft = getLastCommonParent1(root.left, n1, n2);
        TreeNode commonInRight = getLastCommonParent1(root.right, n1, n2);

        //如果一個在左子樹找到一個在右子樹找到，則為root
        if(commonInLeft != null && commonInRight != null) {
            return root;
        }
        //其他情況要不然在左子樹要不然在右子樹
        if(commonInLeft != null) {
            return commonInLeft;
        }
        return commonInRight;
    }

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

/**
     * 獲取兩個節(jié)點的最低公共祖先節(jié)點，復雜度比較低，也是面試官想看到的解法
     *      算法思路：
     *          1）分別獲得一條從根節(jié)點到指定節(jié)點的路徑，該過程需要輔助空間List來存放路徑上的節(jié)點
     *          2）求這兩條路徑的最后一個橡膠的節(jié)點即為題目想要找到的節(jié)點
     *      得到兩條路在最壞情況下的時間復雜度是O(n),通常情況下兩條路徑的長度是O(logn)
     */
    public static TreeNode getLastCommonParent2(TreeNode root, TreeNode n1, TreeNode n2) {
        if(root == null || n1 == null || n2 == null) {
            return null;
        }
        ArrayList<TreeNode> path1 = new ArrayList<>();
        getNodePath(root, n1, path1);
        ArrayList<TreeNode> path2 = new ArrayList<>();
        getNodePath(root, n2, path2);

        return getCommonNode(path1, path2);

    }

    //獲得兩條路徑的最后一個公共節(jié)點
    public static TreeNode getCommonNode(List<TreeNode> path1, List<TreeNode> path2) {
        int i = 0;
        TreeNode res = null;
        while (i < path1.size() && i < path2.size()) {
            if(path1.get(i) == path2.get(i)) {
                res = path1.get(i);
                i  ;
            }
            else {
                break;
            }
        }
        return res;
    }

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

11.求二叉樹中節(jié)點的最大距離

    /**
     * 求二叉樹中節(jié)點的最大距離 即二叉樹中相距最遠的兩個節(jié)點之間的距離。 (distance / diameter)
     * 遞歸解法：
     * （1）如果二叉樹為空，返回0，同時記錄左子樹和右子樹的深度，都為0
     * （2）如果二叉樹不為空，最大距離要么是左子樹中的最大距離，要么是右子樹中的最大距離，
     * 要么是左子樹節(jié)點中到根節(jié)點的最大距離 右子樹節(jié)點中到根節(jié)點的最大距離，
     * 
     * 同時記錄左子樹和右子樹節(jié)點中到根節(jié)點的最大距離。
     *
     * http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html
     *
     * 計算一個二叉樹的最大距離有兩個情況:

     情況A: 路徑經過左子樹的最深節(jié)點，通過根節(jié)點，再到右子樹的最深節(jié)點。
     情況B: 路徑不穿過根節(jié)點，而是左子樹或右子樹的最大距離路徑，取其大者。
     只需要計算這兩個情況的路徑距離，并取其大者，就是該二叉樹的最大距離
     */
    public static Result getMaxDistance(TreeNode root) {
        if(root == null) {
            Result empty = new Result(0, -1);   // 目的是讓調用方  1 后，把當前的不存在的 (NULL) 子樹當成最大深度為 0
            return empty;
        }
        //計算出左右子樹分別最大距離
        Result lmd = getMaxDistance(root.left);
        Result rmd = getMaxDistance(root.right);

        Result res = new Result();
        res.maxDepth = Math.max(lmd.maxDepth, rmd.maxDepth) 1;  //計算最大深度
        //取情況A和情況B中較大值
        res.maxDistance = Math.max(lmd.maxDepth rmd.maxDepth, Math.max(lmd.maxDistance, rmd.maxDistance));
        return res;
    }

    private static class Result {
        int maxDistance;
        int maxDepth;
        public Result() {

        }
        public Result(int maxDistance, int maxDepth) {
            this.maxDistance = maxDistance;
            this.maxDepth = maxDepth;
        }
    }

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

12.把從根節(jié)點出發(fā)到node節(jié)點的路徑所有經過的節(jié)點添加到路徑path中

    /**
     * 把從根節(jié)點出發(fā)到node節(jié)點的路徑所有經過的節(jié)點添加到路徑path中
     */
    public static boolean getNodePath(TreeNode root, TreeNode node, ArrayList<TreeNode> path) {
        if(root == null) {
            return false;
        }
        path.add(root); //先將根節(jié)點添加到路徑中
        if(root == node) {
            return true;
        }
        boolean found = getNodePath(root.left, node, path); //在左子樹中找node節(jié)點
        if(!found) {    //左子樹中沒有node節(jié)點，在右子樹中查找
            found = getNodePath(root.right, node, path);
        }
        if(!found) {    //如果左右子樹中都不存在node節(jié)點，則將之前加到path中的root節(jié)點刪除
            path.remove(root);
        }
        return found;
    }

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

13.重建二叉樹

    /**
     * 根據(jù)前序遍歷序列和中序遍歷序列重建二叉樹
     */
    public static TreeNode rebuildBinaryTreeByPreAndIn(List<TreeNode> preOrder, List<TreeNode> inOrder) {
        TreeNode root = null;   //定義二叉樹根節(jié)點
        List<TreeNode> leftPreOrder;    //左子樹前序遍歷序列
        List<TreeNode> rightPreOrder;   //右子樹前序遍歷序列
        List<TreeNode> leftInOrder;     //左子樹中序遍歷序列
        List<TreeNode> rightInOrder;    //右子樹中序遍歷序列
        int preNum = 0;
        int inNum = 0;

        if((!preOrder.isEmpty()) && (!inOrder.isEmpty())) {
            root = preOrder.get(0); //前序遍歷的第一個節(jié)點即為根節(jié)點

            //根據(jù)root的位置，可以確定inOrder左邊的是左子樹序列，右邊的是右子樹序列
            inNum = inOrder.indexOf(root);  //找到root在inOrder中的位置
            leftInOrder = inOrder.subList(0, inNum);    //左子樹中序遍歷序列
            rightInOrder = inOrder.subList(inNum 1, inOrder.size());    //右子樹中序遍歷序列

            preNum = leftInOrder.size();    //前序序列的分割點
            leftPreOrder = preOrder.subList(1, preNum 1);
            rightPreOrder = preOrder.subList(preNum 1, preOrder.size());

            root.left = rebuildBinaryTreeByPreAndIn(leftPreOrder, leftInOrder);   // root的左子樹就是preorder和inorder的左側區(qū)間而形成的樹
            root.right = rebuildBinaryTreeByPreAndIn(rightPreOrder, rightInOrder);
        }
        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

    /**
     * 根據(jù)中序和后序遍歷序列重建二叉樹
     */
    public static TreeNode rebuildBinaryTreeByInAndPost(List<TreeNode> inOrder, List<TreeNode> postOrder) {
        TreeNode root = null;   //新建根節(jié)點
        List<TreeNode> leftInOrder;
        List<TreeNode> rightInOrder;
        List<TreeNode> leftPostOrder;
        List<TreeNode> rightPostOrder;
        int inNum = 0;
        int postNum = 0;

        if((inOrder.size() != 0) && (postOrder.size() != 0)) {
            root = postOrder.get(postOrder.size()-1);   //后序遍歷序列的最后一個節(jié)點即為根節(jié)點

            //由root節(jié)點的位置可以分割中序遍歷序列
            inNum = inOrder.indexOf(root);
            leftInOrder = inOrder.subList(0, inNum);
            rightInOrder = inOrder.subList(inNum 1, inOrder.size());

            postNum = leftInOrder.size();   //后序遍歷序列的左右子樹分割點
            leftPostOrder = postOrder.subList(0, postNum);
            rightPostOrder = postOrder.subList(postNum, postOrder.size());

            root.left = rebuildBinaryTreeByInAndPost(leftInOrder, leftPostOrder);
            root.right = rebuildBinaryTreeByInAndPost(rightInOrder, rightPostOrder);
        }
        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

14.判斷二叉樹是否為完全二叉樹

    /**
     * 判斷二叉樹是否為完全二叉樹，迭代
     *  若設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數(shù)都達到最大個數(shù)，
     第 h 層所有的結點都連續(xù)集中在最左邊，這就是完全二叉樹。
     有如下算法，按層次（從上到下，從左到右）遍歷二叉樹，當遇到一個節(jié)點的左子樹為空時，
     則該節(jié)點右子樹必須為空，且后面遍歷的節(jié)點左右子樹都必須為空，否則不是完全二叉樹。
     */
    public static boolean isCompleteBinaryTree1(TreeNode root) {
        if(root == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean mastHaveNoChild = false;
        boolean result = false;

        while (!queue.isEmpty()) {
            TreeNode cur = queue.remove();  //隊列先進先出
            if(mastHaveNoChild){    // 已經出現(xiàn)了有空子樹的節(jié)點了，后面出現(xiàn)的必須為葉節(jié)點（左右子樹都為空）
                if(cur.left != null || cur.right != null) {
                    result = false;
                    break;
                }
            }
            else {
                if(cur.left == null && cur.right != null) { //如果左子樹為空，右子樹非空則說明不是完全二叉樹
                    result = false;
                    break;
                }
                else if(cur.left != null && cur.right == null) {    //如果左子樹非空，右子樹為空，則左子節(jié)點不能有左右子樹
                    mastHaveNoChild = true;
                    queue.add(cur.left);
                }
                else if(cur.left != null && cur.right != null) {    //如果左右子孩子都非空，則加入隊列繼續(xù)循環(huán)
                    queue.add(cur.left);
                    queue.add(cur.right);
                }
                else {  // 如果左右子樹都為空，則后面的必須也都為空子樹
                    mastHaveNoChild = true;
                }
            }
        }
        return result;
    }

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

    /**
     * 判斷二叉樹是否是完全二叉樹，遞歸解法
     */
    public static boolean isCompleteBinaryTree2(TreeNode root) {
        return isCompleteTree(root).height != -1;
    }

    public static Pair isCompleteTree(TreeNode root) {
        if(root == null) {
            return new Pair(0, true);
        }
        Pair left = isCompleteTree(root.left);
        Pair right = isCompleteTree(root.right);

        //如果左樹是滿樹，且左右子樹同高度，則是唯一可能形成滿樹（右樹也是滿樹）的情況
        if(left.isFull && left.height == right.height) {
            return new Pair(1 left.height, right.isFull);
        }

        //左樹非滿，但右樹是滿樹，且左樹比右樹高度高1
        if(right.isFull && left.height == right.height  1) {
            return new Pair(left.height 1, false);
        }
        //其他情況都不是完全二叉樹
        return new Pair(-1, false);
    }

    private static class Pair {
        int height; //樹的高度
        boolean isFull; //是否是滿樹

        public Pair(int height, boolean isFull) {
            this.height = height;
            this.isFull = isFull;
        }
    }

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

15.判斷二叉樹B是不是二叉樹A的子結構

    /**
     * 兩顆二叉樹A,B，判斷B是不是A的子樹
     *
     * 解題思路：
     *      1）在樹A中找到樹B的根節(jié)點值一樣的節(jié)點R
     *      2）判斷A中以R為根節(jié)點的子樹是不是包含和樹B一樣的結構
     */
    public static boolean isSubTree(TreeNode root1, TreeNode root2) {
        boolean result = false;
        if(root1 != null && root2 != null) {    //兩顆二叉樹都不為空的時候
            //如果在A中找到和B的根節(jié)點值相同的節(jié)點R，則調用doseTree1HasTree2做第二步判斷
            if(root1.val == root2.val) {
                result = doseTree1HasTree2(root1, root2);
            }
            //如果在A中沒有找到和B的根節(jié)點相同的節(jié)點R，則遞歸遍歷左右子樹尋找
            if(!result) {
                result = isSubTree(root1.left, root2);
            }
            if(!result) {
                result = isSubTree(root1.right, root2);
            }
        }
        return result;
    }

    //第二步，判斷A中以R為根節(jié)點的子樹是不是和樹B有相同的結構
    public static boolean doseTree1HasTree2(TreeNode root1, TreeNode root2) {
        //這里一定是root2的判斷在前，若先判斷root1則可能會出現(xiàn)root1和root2都為空的情況，此時返回的是false答案將會是錯誤的，所以一定要先判斷root2
        if(root2 == null) {
            return true;
        }
        if(root1 == null) {
            return false;
        }
        if(root1.val != root2.val) {
            return false;
        }

        //遞歸判斷他們左右子節(jié)點的值是否相同
        return doseTree1HasTree2(root1.left, root2.left) &&
                doseTree1HasTree2(root1.right, root2.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

16.二叉樹的鏡像

    /**
     * 求一棵二叉樹的鏡像
     *
     * 解題過程：（遞歸）
     *     先前序遍歷這棵樹的每個節(jié)點，如果遍歷到的節(jié)點有子節(jié)點，則交換兩個子節(jié)點（同時也是交換了它的左右子樹），
     *     當交換完所有非葉子結點的子節(jié)點以后，就得到了樹的鏡像
     * 該解法會破壞原二叉樹的結構
     */
    public static void mirrorTree(TreeNode root) {
        //如果該樹為空樹或者是只有一個節(jié)點的樹，則直接返回
        if(root == null || (root.left == null && root.right == null)) {
            return;
        }
        //交換左右子節(jié)點
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        if(root.left != null) { //如果左子節(jié)點存在
            //遞歸遍歷左子樹
            mirrorTree(root.left);
        }
        if(root.right != null) {
            mirrorTree(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

    /**
     * 求一棵二叉樹的鏡像
     *
     *  迭代解法
     *  仍然采用前序遍歷的方法，用棧來實現(xiàn)
     */
    public static void mirrorTree2(TreeNode root) {
        if(root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();

            TreeNode temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;

            if(cur.right != null) { //前序遍歷，先壓入右節(jié)點，再壓入左節(jié)點
                stack.push(cur.right);
            }
            if(cur.left != null) {
                stack.push(cur.left);
            }
        }
    }

?

//不改變原二叉樹的迭代解法
    public static TreeNode mirrorTree3(TreeNode root) {
        if(root == null) {
             return null;
        }
        TreeNode newRoot = new TreeNode(root.val);

        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> newStack = new Stack<>();
        stack.push(root);
        newStack.push(newRoot);

        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            TreeNode newCur = newStack.pop();

            if(cur.right != null) {
                stack.push(cur.right);
                newCur.left = new TreeNode(cur.right.val);
                newStack.push(newCur.left);
            }
            if(cur.left != null) {
                stack.push(cur.left);
                newCur.right = new TreeNode(cur.left.val);
                newStack.push(newCur.right);
            }
        }
        return newRoot;
    }

17.判斷一個序列是否是二叉搜索樹的后序遍歷序列

    /**
     * 判斷一個序列是否是二叉搜索樹的后序遍歷序列
     *
     *  根據(jù)后序遍歷序列的規(guī)則，最后一個元素即根元素，比根元素小的是左子樹，大的是右子樹，然后遞歸判斷
     *
     *  @param start    起始索引下標
     *  @param end      結束索引下標
     */
    public static boolean verifySequenceOfBST(int[] sequence, int start, int end) {
        if(sequence == null || start < 0 || end <= 0) {
            return false;
        }

        int root = sequence[end];   //根節(jié)點就是最后一個元素
        //在二叉搜索樹中左子樹的節(jié)點都比右子樹小
        int i = 0;
        for (; i < end; i  ) {
            if(sequence[i] > root) {
                break;
            }
        }

        //在二叉搜索樹中右子樹的節(jié)點大于根節(jié)點
        int j = i;  //右子樹的第一個元素（序列中的元素）
        for (; j < end; j  ) {
            if(sequence[j] < root) {
                return false;
            }
        }

        //判斷左子樹是不是二叉搜索樹
        boolean left = true;
        i--;
        if(i > 0) {
            left = verifySequenceOfBST(sequence, 0, i);
        }

        //判斷右子樹是不是二叉搜索樹
        boolean right = true;
        i  ;
        if(i < end) {
            right = verifySequenceOfBST(sequence, i, end-1);
        }
        return (left && 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

18.求二叉樹中和為某一值的路徑

    /**
     * 求二叉樹中和為某一值的路徑
     *      題目描述：從樹的根節(jié)點開始往下一直到葉節(jié)點所經過的節(jié)點形成一條路徑
     *
     * 解題思路：
     *      用前序遍歷的方式訪問某一節(jié)點時，把該節(jié)點加入到路徑上，并且累加該節(jié)點的值。
     *      如果該節(jié)點為葉子節(jié)點并且路徑中節(jié)點值的和剛好等于輸入的整數(shù)，則當前路徑符合要求，可以打印出來；
     *      如果當前節(jié)點不是葉子節(jié)點，則繼續(xù)訪問它的子節(jié)點。
     *      當前節(jié)點訪問結束后，遞歸函數(shù)自動回到它的父節(jié)點。（實際可以用棧來滿足）
     *      因此在退出之前要在路徑上刪除當前節(jié)點，并且減去當前節(jié)點的值，以確保返回父節(jié)點時路徑剛好是從根節(jié)點到父節(jié)點的路徑
     */
    public static void findPath(TreeNode root, int sum) {
        if(root == null) {
            return;
        }
        int currentSum = 0;
        //用java里面LinkedList的add和removeLast方法實現(xiàn)棧的先進后出特性，這樣方便和面打印路徑
        LinkedList<Integer> path = new LinkedList<>();    //用于存儲路徑


        findPathTemp(root, sum, path, currentSum);
    }
    public static void findPathTemp(TreeNode root, int sum, LinkedList<Integer> path, int currentSum) {
        currentSum  = root.val;
        path.addLast(root.val);

        //如果是葉子節(jié)點，并且路徑上節(jié)點值的和等于輸入的整數(shù)
        boolean isLeaf = false;
        if(root.left == null && root.right == null) {
            isLeaf = true;
        }
        if(currentSum == sum && isLeaf) {
            System.out.println("A path is found:");
            for (int i = 0; i < path.size(); i  ) {
                System.out.printf("%d\t", path.get(i));
            }
            System.out.println();
        }

        //如果不是葉子節(jié)點，則遍歷它的子節(jié)點
        if(root.left != null) {
            findPathTemp(root.left, sum, path, currentSum);
        }
        if(root.right != null) {
            findPathTemp(root.right, sum, path, currentSum);
        }
        //在返回父節(jié)點之前，在路徑上刪除當前節(jié)點
        path.removeLast();
    }

來源：http://www./content-4-145301.html

本站是提供個人知識管理的網絡存儲空間，所有內容均由用戶發(fā)布，不代表本站觀點。請注意甄別內容中的聯(lián)系方式、誘導購買等信息，謹防詐騙。如發(fā)現(xiàn)有害或侵權內容，請點擊一鍵舉報。

小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看