目錄

概念（在做習(xí)題中常用的概念）

兩種特殊的二叉樹(shù)

二叉樹(shù)的性質(zhì)

二叉樹(shù)的遍歷（重點(diǎn)）

如上圖：

二叉樹(shù)的構(gòu)建（代碼表示一顆二叉樹(shù)和一些操作二叉樹(shù)的方法）

二叉樹(shù)的oj習(xí)題講解（重點(diǎn)）

1. 檢查兩棵樹(shù)是否相同?力扣

2. 另一顆樹(shù)的子樹(shù)? ?力扣

3. 反轉(zhuǎn)二叉樹(shù)? ??力扣

4. 判斷一顆二叉樹(shù)是否為平衡二叉樹(shù)（ 分別在O（N*2）和O（N）的時(shí)間復(fù)雜度代碼來(lái)寫(xiě) ）? ??力扣

5. 對(duì)稱(chēng)二叉樹(shù)? ?力扣

6. 二叉樹(shù)的構(gòu)建及遍歷（根據(jù)先序遍歷創(chuàng)建一顆二叉樹(shù)）? ?二叉樹(shù)遍歷_?？皖}霸_?？途W(wǎng)

7. 二叉樹(shù)的層序遍歷? ?力扣

8. 二叉樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先? ?力扣

9. 根據(jù)前序遍歷和中序遍歷構(gòu)造一顆二叉樹(shù)? ?力扣

10. 根據(jù)后序遍歷和中序遍歷構(gòu)建一顆二叉樹(shù)? ?力扣

11. 二叉樹(shù)創(chuàng)建字符串? ?力扣

12. 二叉樹(shù)的前序 非遞歸遍歷? ?力扣

13. 二叉樹(shù)的中序 非遞歸遍歷? ?力扣

14. 二叉樹(shù)的后序 非遞歸遍歷? ?力扣

oj題代碼詳解：

前言

? ? 二叉樹(shù)的一些oj題是在面試中?？嫉?，同時(shí)概念也是很重要的，在做二叉樹(shù)習(xí)題中掌握概念以及一些推導(dǎo)公式才能提高做題效率。

概念（在做習(xí)題中常用的概念）

二叉樹(shù)如何用代碼表示（定義一個(gè)靜態(tài)內(nèi)部類(lèi)）

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

? ? 由于二叉樹(shù)每個(gè)節(jié)點(diǎn)都有值域（value）、左子樹(shù)（left）、右子樹(shù)（right），所以將二叉樹(shù)的節(jié)點(diǎn)定義成一個(gè)靜態(tài)內(nèi)部類(lèi)，加上構(gòu)造方法，就構(gòu)成一顆二叉樹(shù)中的完整的一個(gè)節(jié)點(diǎn)。

?兩種特殊的二叉樹(shù)

1. 滿二叉樹(shù)

? ? ?每層節(jié)點(diǎn)數(shù)都達(dá)到最大值，這顆二叉樹(shù)就是滿二叉樹(shù)，或者一顆二叉樹(shù)的層數(shù)為k，且節(jié)點(diǎn)總數(shù)是2^k - 1，此時(shí)這棵樹(shù)就是滿二叉樹(shù)。

2. 完全二叉樹(shù)

? ? 完全二叉樹(shù)是由滿二叉樹(shù)引出的，從根節(jié)點(diǎn)開(kāi)始編號(hào)，順序從上往下，每一行是從左往右，沒(méi)有編號(hào)為空的節(jié)點(diǎn)，此時(shí)這棵樹(shù)就是完全二叉樹(shù)。

二叉樹(shù)的性質(zhì)

?二叉樹(shù)的遍歷（重點(diǎn)）

如上圖：

? ? 1. 先序遍歷： 1 2 4 5 3 6 7

? ? 2. 中序遍歷： 4 2 5 1 6 3 7

? ? 3. 后序遍歷：?4 5 2 6 7 3 1

? ? 4. 層序遍歷： 1 2 3 4 5 6 7

二叉樹(shù)的構(gòu)建（代碼表示一顆二叉樹(shù)和一些操作二叉樹(shù)的方法）

public class TextBinaryTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode root;//定義二叉樹(shù)的根節(jié)點(diǎn)
    //非正規(guī)創(chuàng)建一顆二叉樹(shù)
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = H;
        C.left = F;
        C.right = G;
        this.root = A;
        return root;
    }
    //前序遍歷
    public void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //中序遍歷
    public void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    //后序遍歷
    public void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    //前序遍歷有返回值
    //此時(shí)這個(gè)list需要放在外邊，否則每次遞歸都會(huì)產(chǎn)生一個(gè)新的list
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return list;
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
    //二叉樹(shù)的中序遍歷有返回值
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        List<Integer> leftTree = inorderTraversal(root.left);
        list.addAll(leftTree);
        list.add(root.val);
        List<Integer> rightTree = inorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }
    //二叉樹(shù)的后序遍歷有返回值
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        List<Integer> leftTree = postorderTraversal(root.left);
        list.addAll(leftTree);
        List<Integer> rightTree = postorderTraversal(root.right);
        list.addAll(rightTree);
        list.add(root.val);
        return list;
    }
    //獲取二叉樹(shù)中的節(jié)點(diǎn)個(gè)數(shù)
    //子問(wèn)題：左樹(shù)的節(jié)點(diǎn) + 右樹(shù)的節(jié)點(diǎn) + 1
    //時(shí)間復(fù)雜度：O(N)  空間復(fù)雜度：O(logN)，如果是單分支的樹(shù)，空間復(fù)雜度就是
    //O（N）
    public int size(TreeNode root) {
        if (root == null) return 0;
        return size(root.left) + size(root.right) + 1;
    }
    //遍歷思路
    public int count = 0;
    public int size1(TreeNode root) {
        if (root == null) return 0;
        //只要根不為空就++，然后遍歷左樹(shù)和右樹(shù)
        count++;
        size1(root.left);
        size1(root.right);
        return count;
    }
    //獲取葉子節(jié)點(diǎn)的個(gè)數(shù)   子問(wèn)題思路
    public int getLeafNodeCount(TreeNode root) {
        if (root == null) return 0;//注意：當(dāng)root為空的時(shí)候是沒(méi)有葉子節(jié)點(diǎn)的
        if (root.left == null && root.right == null)
            return 1;
        return getLeafNodeCount(root.left) +
                getLeafNodeCount(root.right);
    }
    //遍歷思路
    public int leafCount;
    public void leafNodeCount(TreeNode root) {
        if (root == null) return;
        if (root.left == null && root.right == null)
            leafCount++;
        leafNodeCount(root.left);
        leafNodeCount(root.right);
    }
    //獲取第k層的節(jié)點(diǎn)個(gè)數(shù)
    //第k層的節(jié)點(diǎn)個(gè)數(shù)就相當(dāng)于第k-1層的孩子的節(jié)點(diǎn)個(gè)數(shù)
    public int getLevelNodeCount(TreeNode root, int k) {
        if (root == null) return 0;
        if (k == 1) return 1;
        int left = getLevelNodeCount(root.left, k-1);
        int right = getLevelNodeCount(root.right, k-1);
        return left + right;
    }
    //獲取二叉樹(shù)的高度
    //時(shí)間復(fù)雜度：O（n）（會(huì)遍歷到每一個(gè)節(jié)點(diǎn)）
    public int getHeight(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight,rightHeight) + 1;
    }
    //二叉樹(shù)的層序遍歷
    public void levelOrder1(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);
            }
        }
    }
    //二叉樹(shù)層序遍歷有返回值
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> ret = new ArrayList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                ret.add(cur.val);
                size--;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(ret);
        }
        return list;
    }
}

二叉樹(shù)的oj習(xí)題講解

oj題代碼詳解：

//二叉樹(shù)的構(gòu)建及遍歷：讀入一顆先序遍歷的字符串，創(chuàng)建一顆二叉樹(shù)
    //然后按中序遍歷輸出二叉樹(shù)的節(jié)點(diǎn)
    //雖然只是一個(gè)前序遍歷的字符串，但是也是可以創(chuàng)建出一顆二叉樹(shù)的（有順序的前序遍歷）
    /*此處的字符串下標(biāo)是不會(huì)越界的，因?yàn)榻o的前序遍歷本來(lái)就是一個(gè)合法的字符串，如果多給了
    * 或者是少給了，此時(shí)在創(chuàng)建右樹(shù)的時(shí)候就會(huì)發(fā)生越界，因?yàn)樽址呀?jīng)遍歷完了，但是可能樹(shù)
    * 還沒(méi)有建完，所以還會(huì)遞歸，但是現(xiàn)在是合法的字符串，此時(shí)遞歸的時(shí)候有回退的次數(shù)*/
    public static void main(String[] args) {
        //在main方法中將i置零也是可以的，
        Scanner scan = new Scanner(System.in);
        //將字符串整行都讀進(jìn)來(lái)
        String str = scan.nextLine();
        TreeNode root = createTree(str);
        inorder(root);
    }
    public static int i = 0;
    public static TreeNode createTree(String str) {
        TreeNode root = null;
        char ch = str.charAt(i);
        if (ch != '#') {
            root = new TreeNode(ch);
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }
    public static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.println(root.val + " ");
        inorder(root.right);
    }
    //二叉樹(shù)的最近公共祖先
    /*1.在根的兩邊 2.要么都在根的左邊或者右邊（其中一個(gè)就是公共祖先）*/
    public TreeNode lowestCommonAncestor(
            TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        /*這個(gè)地方是找到就返回了，如：在左邊先找到了一個(gè)節(jié)點(diǎn)，此時(shí)p和q都在
        * root的左邊，但是找到p就結(jié)束了，不會(huì)再去找另一個(gè)節(jié)點(diǎn)了，所以返回的
        * 節(jié)點(diǎn)就是上邊的節(jié)點(diǎn)，就是最近的公共祖先*/
        else if (left != null) return left;
        else if (right != null) return right;
        else return null;
    }
    //如果每個(gè)節(jié)點(diǎn)有了父親節(jié)點(diǎn)的地址，此時(shí)就變成了求相交節(jié)點(diǎn)
    //但是二叉樹(shù)沒(méi)有父親節(jié)點(diǎn)，所以用一個(gè)數(shù)據(jù)結(jié)構(gòu)：棧
    /*把找p和q的路徑入到兩個(gè)棧中，然后元素多的先出差值個(gè)元素，之后再一起出
    * 如果元素相等此時(shí)這個(gè)元素就是最近公共祖先*/

    //找到從根節(jié)點(diǎn)到指定節(jié)點(diǎn)node路徑上所有的節(jié)點(diǎn)，然后入棧
    public boolean getPath(TreeNode root,
                           TreeNode node, Deque<TreeNode> stack) {
        if (root == null || node == null) return false;
        stack.push(root);
        if (root == node) return true;
        boolean ret1 = getPath(root.left,node,stack);
        boolean ret2 = getPath(root.right,node,stack);
        if (ret1) return true;
        if (ret2) return true;
        //左邊和右邊都沒(méi)找到這個(gè)node，此時(shí)就回退，讓這個(gè)元素出棧
        stack.pop();
        return false;//說(shuō)明這條路徑走不通，走到頭了，也沒(méi)找到這個(gè)節(jié)點(diǎn)
    }
    public TreeNode lowestCommonAncestor2(TreeNode root,
                                          TreeNode p, TreeNode q) {
        //1.兩個(gè)棧中先存儲(chǔ)好數(shù)據(jù)
        Deque<TreeNode> stack1 = new LinkedList<>();
        getPath(root,p,stack1);
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root,q,stack2);
        //2.判斷棧的大小，出差值個(gè)元素
        int size1 = stack1.size();
        int size2 = stack2.size();
        //讓size1是最大的
        int ret = Math.abs(size1 - size2);
        while (ret != 0) {
            if (size1 > size2) {
                stack1.pop();
            }else {
                stack2.pop();
            }
            ret--;
        }
        //棧中元素個(gè)數(shù)相等，此時(shí)一塊出元素
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.peek() != stack2.peek()) {
                stack1.pop();
                stack2.pop();
            }else {
                return stack1.pop();
            }
        }
        return null;
    }
    //根據(jù)前序遍歷和中序遍歷構(gòu)造一顆二叉樹(shù)
    /*1.根據(jù)前序遍歷找到根   2.在中序遍歷中找到根的位置*/
    //public int i = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root = buildTreeChild(preorder, inorder, 0,
                inorder.length - 1);
        return root;
    }
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,
                                   int begin, int end) {
        if (begin > end) return null;//如果下標(biāo)越界，此時(shí)說(shuō)明沒(méi)有節(jié)點(diǎn)了
        //TreeNode root = new TreeNode(preorder[i]);
        //找到當(dāng)前根在中序遍歷中的位置
        int rootIndex = findIndex(inorder,begin, end, preorder[i]);
        i++;
        root.left = buildTreeChild(preorder,inorder,begin,rootIndex-1);
        root.right = buildTreeChild(preorder, inorder, rootIndex+1,end);
        return root;
    }

    private int findIndex(int[] inorder, int begin, int end, int key) {
        for (int j = begin; j <= end; j++) {
            if (key == inorder[j]) return j;
        }
        return -1;
    }
    //根據(jù)中序遍歷和后序遍歷來(lái)創(chuàng)建一顆二叉樹(shù)
    /*1.先從后續(xù)遍歷中找到根，之后在中序遍歷中找到根的位置*/
    /*然后i--，要注意，先創(chuàng)建的是右樹(shù)，然后創(chuàng)建左樹(shù)*/
    public int a;
    public TreeNode buildTree3(int[] inorder, int[] postorder) {
        a = postorder.length - 1;
        TreeNode root = buildChildTree(inorder,postorder,
                 0, inorder.length - 1);
        return root;
    }
    public TreeNode buildChildTree(int[] inorder,int[] postorder,
                                   int begin, int end) {
        //TreeNode root = new TreeNode(postorder[a]);
        int rootIndex = findIndex(inorder, begin, end, postorder[a]);
        a--;
        root.right = buildChildTree(inorder,postorder,rootIndex + 1,end);
        root.left = buildChildTree(inorder, postorder, begin, rootIndex - 1);
        return root;
    }
    //根據(jù)二叉樹(shù)創(chuàng)建字符串
    /*要以前序遍歷的方式來(lái)創(chuàng)建這個(gè)字符串*/
    public String tree2str(TreeNode root) {
        if (root == null) return null;
        StringBuilder builder = new StringBuilder();
        tree2strChild(root, builder);
        /*1.左邊為空，右邊為空  2.左邊不為空右邊為空  3.左邊為空右邊不為空*/
        return builder.toString();
    }
    public void tree2strChild(TreeNode root, StringBuilder builder) {
        if (root == null) return;
        builder.append(root.val);
        //左子樹(shù)為空或者不為空
        if (root.left != null) {
            builder.append("(");
            tree2strChild(root.left,builder);
            builder.append(")");
        }else {
            //左邊為空的情況下考慮右邊
            if (root.right != null) {
                builder.append("()");
            }else {
                return;
            }
        }
        //右子樹(shù)為空或者不為空
        if (root.right != null) {
            builder.append("(");
            tree2strChild(root.right,builder);
            builder.append(")");
        }else {
            return;
        }
    }
    //判斷一棵樹(shù)是否為完全二叉樹(shù)
    //用合適的數(shù)據(jù)結(jié)構(gòu): 隊(duì)列
    /*每次從隊(duì)列中取出一個(gè)節(jié)點(diǎn)，不為空：把左子樹(shù)和右子樹(shù)帶進(jìn)來(lái)，
    * 為空：開(kāi)始判斷隊(duì)列中剩余的元素*/
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                //如果cur為空說(shuō)明左和右都是空的了，此時(shí)就去判斷隊(duì)列中的元素是否都是空的
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if (tmp != null) return false;
        }
        return true;
    }
    //非遞歸實(shí)現(xiàn)前序遍歷
    public List<Integer> preorderTraversalNor(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }
    //非遞歸實(shí)現(xiàn)中序遍歷
    public List<Integer> inorderTraversalNor(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);
            cur = top.right;
        }
        return list;
    }
    //非遞歸實(shí)現(xiàn)后序遍歷
    public List<Integer> postorderTraversalNor(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            //此時(shí)需要注意：當(dāng)打印之后top.right之后就不要再次打印了
            //所以prev記錄的是 是否打印過(guò)top.right這個(gè)節(jié)點(diǎn)
            if (top.right == null || prev == top.right) {
                stack.pop();
                list.add(top.val);
                prev = top;
            }else {
                cur = top.right;
            }
        }
        return list;
    }

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：二叉樹(shù)詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！