二叉樹

二叉樹基礎(chǔ)知識(shí)：可查看http://www.cnblogs.com/polly333/p/4740355.html
層序遍歷：依靠隊(duì)列，沒有遞歸解法?？刹榭?a target="_blank" rel="nofollow">https://www.cnblogs.com/hapjin/p/5409921.html
前中后序遍歷：依靠棧，有遞歸和非遞歸兩種解法

1.求二叉樹根到葉節(jié)點(diǎn)的最短距離

https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/description/
類似maximum-depth-of-binary-tree。不過(guò)注意，如果一個(gè)節(jié)點(diǎn)只有左子樹或只有右子樹。我們不能取左右子樹中最短的，會(huì)取到0(葉子節(jié)點(diǎn)指的是沒有子節(jié)點(diǎn)的節(jié)點(diǎn)），這樣不符合題意。所以二者其一為空時(shí)，就取另一個(gè)的長(zhǎng)度，最為最短長(zhǎng)度。
遞歸解法:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        if(root.left==null){
            return minDepth(root.right)+1;
        }
        if(root.right==null){
            return minDepth(root.left)+1;
        }
        return Math.min(minDepth(root.right)+1,minDepth(root.left)+1);  
    }
}

非遞歸解法：用到了層序遍歷。
根節(jié)點(diǎn)入隊(duì)列。
然后在循環(huán)中判斷隊(duì)列非空時(shí)，彈出隊(duì)列中的節(jié)點(diǎn)，并把節(jié)點(diǎn)的子節(jié)點(diǎn)入隊(duì)列。
curNum用來(lái)記錄一層的節(jié)點(diǎn)數(shù)。
lastNum記錄這層還需要遍歷的節(jié)點(diǎn)數(shù)。當(dāng)lastNum為0時(shí)，說(shuō)明這層已經(jīng)遍歷完，可以層數(shù)+1；
終止條件即為：找到了左右子樹都為空的節(jié)點(diǎn)。
如果是求maximum-depth，則終止條件是queue為空==》即所有的節(jié)點(diǎn)都被遍歷過(guò)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root==null)return 0;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int curNum = 0;
        int lastNum=1;
        int level=1；
        while(!queue.isEmpty()){
            TreeNode temp = queue.poll();
            lastNum--;
            if(temp.left==null&&temp.right==null){
                return level;
            }
            
            if(temp.left!=null){
                queue.add(temp.left);
                curNum++;
            }
            if(temp.right!=null){
                queue.add(temp.right);
                curNum++;
            }
            if(lastNum==0){
                lastNum=curNum;
                curNum=0;
                level++;
            }
        }
        return 0;
    }
}

要點(diǎn)：

  1. 遞歸解法：需要注意判斷子節(jié)點(diǎn)左右節(jié)點(diǎn)其中一個(gè)為空的情況
  2. 非遞歸解法：用linkedList作為隊(duì)列；記錄層中節(jié)點(diǎn)數(shù)，遍歷完一層，層數(shù)+1；

關(guān)于LinkedList

  1. poll()和pop()都是取first并刪除，隊(duì)列為空時(shí)前者返回null，后者返回NoSuchElementException。本質(zhì)都是調(diào)用unLinkList()
  2. offer(),add()都是向隊(duì)列中添加元素到末尾。offer調(diào)了add。返回值為true，實(shí)際調(diào)用linkLast()。
    push是添加元素到開頭。實(shí)際調(diào)用linkFirst()。無(wú)返回值

2.求二叉樹根到葉節(jié)點(diǎn)的最大距離

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/description/
非遞歸解法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null)return 0;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int curNum=0;
        int lastNum=1;
        int level =0;
        while(!queue.isEmpty()){
            TreeNode temp = queue.poll();
            lastNum--;
            if(temp.left!=null){
                queue.add(temp.left);
                curNum++;
            }
            if(temp.right!=null){
                queue.add(temp.right);
                curNum++;
            }
            if(lastNum==0){
                lastNum=curNum;
                curNum=0;
                level++;
            }
        }
        return level;  
    }
}

要點(diǎn)：這次的level初始值為0。原因就在于max不會(huì)提前判斷葉子節(jié)點(diǎn)，葉子節(jié)點(diǎn)會(huì)走到最后level++的里面，所以不需要直接+1

3.對(duì)稱二叉樹的判斷

https://leetcode-cn.com/problems/symmetric-tree/description/

遞歸解法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null)return true;
        return ST(root.left,root.right);
    }
    
    private boolean ST(TreeNode left,TreeNode right){
        if(left==null&&right==null)return true;
        else if(left==null||right==null)return false;
        else if(left.val!=right.val)return false;
        else{
            return ST(left.left,right.right)&&ST(left.right,right.left);
        }
    }
}

要點(diǎn)：遞歸式在于左樹的左孩子和右樹的右孩子判對(duì)稱；左樹的右孩子和右樹的左孩子判對(duì)稱。終止條件在于兩邊孩子都是null的時(shí)候，left.val=right.val即返回true。
時(shí)間復(fù)雜度： 本質(zhì)其實(shí)就是DFS,時(shí)間復(fù)雜度為O(n)
空間復(fù)雜度： O(h)

迭代解法

利用兩個(gè)隊(duì)列來(lái)完成。
要點(diǎn)：對(duì)稱樹實(shí)際上是判斷左樹和右樹是否對(duì)稱。以根節(jié)點(diǎn)為中軸線，左邊的存入leftQueue,右邊的存入rightQueue；存入順序記得對(duì)稱，一一進(jìn)行比對(duì)
注意：此處不能直接左右為空返回true，因?yàn)樾枰M(jìn)一步的判斷

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null)return true;
        return ST(root);
    }
    
    private boolean ST(TreeNode root){
        if(root==null)return true;
        LinkedList<TreeNode> leftQueue=new LinkedList<TreeNode>();
        LinkedList<TreeNode> rightQueue=new LinkedList<TreeNode>();
        leftQueue.add(root.left);
        rightQueue.add(root.right);
        while(!leftQueue.isEmpty()&&!rightQueue.isEmpty()){
            TreeNode left=leftQueue.poll();
            TreeNode right=rightQueue.poll();
            if(left==null&&right==null)continue;
            else if(left==null&&right!=null||right==null&&left!=null)return false;
            else if(left.val!=right.val)return false;
            else{
                leftQueue.add(left.left);
                leftQueue.add(left.right);
                rightQueue.add(right.right);
                rightQueue.add(right.left);
            }
        }
        return true; 
    }
}

4.N叉樹后序遍歷

迭代解法：

1.用棧
2.打印條件是：沒有孩子（最終節(jié)點(diǎn)）或者上一個(gè)節(jié)點(diǎn)是它的孩子（孩子節(jié)點(diǎn)打完，需要打印上層節(jié)點(diǎn)）
3.放入時(shí)從右向左放節(jié)點(diǎn)，與讀取順序相反
如果是前序遍歷，則不需要if判斷，直接pop打印即可

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> resultList = new LinkedList<Integer>();
        if(root==null)return resultList;
        Stack<Node> stack =new Stack<Node>();
        stack.push(root);
        Node pre=null;
        Node cur=null;
        while(!stack.isEmpty()){
            cur = stack.peek();
            if(pre!=null && cur.children.contains(pre) || cur.children.isEmpty()){
                resultList.add(cur.val);
                stack.pop();
                pre=cur;
            }else{
                int length=cur.children.size();
                for(int i=0;i<cur.children.size();i++){
                    stack.push(cur.children.get(length-i-1));
                }
            }
        }
        return resultList;
    }
}

遞歸解法

dfs，會(huì)遍歷到最下面的節(jié)點(diǎn)，然后打印。保證先打出來(lái)的就是最下層。而且是先遍歷到左節(jié)點(diǎn)的最下層，才會(huì)遍歷右節(jié)點(diǎn)。
如果是前序遍歷，則把 res.add(root.val);提到for循環(huán)之前

class Solution {
     public void dfs(List<Integer> res,Node root){
        if(root==null){
            return;
        }
        for(Node x:root.children){
            dfs(res,x);
        }
         res.add(root.val);
    }
    public List<Integer> postorder(Node root)  {
        List<Integer> res = new ArrayList<Integer>();
        dfs(res,root);
        return res;
    }
}

5.中序遍歷

要點(diǎn)：
1.使用棧
2.入棧當(dāng)前節(jié)點(diǎn)，并將左子節(jié)點(diǎn)置為下個(gè)遍歷節(jié)點(diǎn)。while循環(huán)結(jié)束時(shí)，所有的左子節(jié)點(diǎn)都入棧。
3.出棧時(shí)，pop節(jié)點(diǎn)打印。并將右子節(jié)點(diǎn)設(shè)為下個(gè)遍歷節(jié)點(diǎn)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> res = new LinkedList<Integer>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root==null)return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            //取出節(jié)點(diǎn)，并把當(dāng)前節(jié)點(diǎn)設(shè)成取出節(jié)點(diǎn)的右子節(jié)點(diǎn)
            if(!stack.isEmpty()){
                cur=stack.pop();
                res.add(cur.val);
                cur=cur.right;
            } 
        }
        return res;
    }
}

6.層次遍歷

遞歸方式

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        set(root, 0, result);
        return result;
    }

    public void set(TreeNode treeNode, int level, List<List<Integer>> result) {
        if(treeNode==null){
            return;
        }
        if(level==result.size()){
            result.add(new ArrayList<>());
        }
        result.get(level).add(treeNode.val);
        set(treeNode.left,level+1,result);
        set(treeNode.right,level+1,result);
    }
}

非遞歸方式

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<List<Integer>> res = new LinkedList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        if(root==null)return res;
        queue.add(root);
        int curNum=0;
        int lastNum=1;
        while(!queue.isEmpty()){
            List<Integer> tempList = new LinkedList<Integer>();
            while(lastNum!=0){
                TreeNode temp = queue.pop();
                tempList.add(temp.val);
                if(temp.left!=null){
                    queue.add(temp.left);
                    curNum++;
                }
                if(temp.right!=null){
                    queue.add(temp.right);
                    curNum++;
                }
                lastNum--;
            }
            lastNum=curNum;
            curNum=0;
            res.add(tempList);
        }
        return res;
    }
}

變形題：二叉樹的右視圖
https://leetcode-cn.com/problems/binary-tree-right-side-view/description/
只取每層的最后一個(gè)節(jié)點(diǎn)

7.翻轉(zhuǎn)二叉樹

https://leetcode-cn.com/problems/invert-binary-tree/description/
遞歸解法：
1.翻轉(zhuǎn)左右節(jié)點(diǎn)
2.翻轉(zhuǎn)左右子樹

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null)return null;
        TreeNode temp=root.right;
        root.right=root.left;
        root.left=temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

8.平衡二叉樹的判斷

遞歸方式：
用maximum-depth的方法求樹高度。
判斷根節(jié)點(diǎn)的左右兩子樹高度差是否大于1，若大于1則非平衡樹，返回false;否則，繼續(xù)遞歸的判斷其左子樹和右子樹是否是平衡樹。
這樣做會(huì)重復(fù)遍歷多次節(jié)點(diǎn)。求一個(gè)節(jié)點(diǎn)的深度是O(lgn)，所以求所有節(jié)點(diǎn)的就是O(nlgn)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null)return true;
        int left = treeDepth(root.left);
        int right = treeDepth(root.right);
        if(Math.abs(left-right)>1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
    }
    private int treeDepth(TreeNode root){
        if(root==null)return 0;
        int left = treeDepth(root.left);
        int right= treeDepth(root.right);
        return Math.max(left,right)+1;
    }
}

上面那個(gè)方法正確但不是很高效，因?yàn)?strong>每一個(gè)點(diǎn)都會(huì)被上面的點(diǎn)計(jì)算深度時(shí)訪問一次，我們可以進(jìn)行優(yōu)化。方法是如果我們發(fā)現(xiàn)子樹不平衡，則不計(jì)算具體的深度，而是直接返回-1。那么優(yōu)化后的方法為：對(duì)于每一個(gè)節(jié)點(diǎn)，我們通過(guò)checkDepth方法遞歸獲得左右子樹的深度，如果子樹是平衡的，則返回真實(shí)的深度，若不平衡，直接返回-1，此方法時(shí)間復(fù)雜度O(N)，空間復(fù)雜度O(H)，參見代碼如下：
要點(diǎn)在于計(jì)算高度的時(shí)候順便算出是否平衡，同一個(gè)節(jié)點(diǎn)不需要遍歷兩次

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        int height = checkDepth(root);
        if(height>=0){
            return true;
        }else{
            return false;
        }
        
    }
    private int checkDepth(TreeNode root){
        if(root==null)return 0;
        int left = checkDepth(root.left);
        int right= checkDepth(root.right);
        if(left==-1||right==-1)return -1;
        if(Math.abs(left-right)>1){
            return -1;
        }else{
            return Math.max(left,right)+1;
        }
    }
}

9.二叉樹剪枝

https://leetcode-cn.com/problems/binary-tree-pruning/description/
思路：
1.如果本身為1，保留這個(gè)節(jié)點(diǎn)。對(duì)其左右節(jié)點(diǎn)進(jìn)行剪枝
2.如果左右節(jié)點(diǎn)剪枝不為空，那么保留這個(gè)節(jié)點(diǎn)
3.如果左右節(jié)點(diǎn)剪枝為空，說(shuō)明節(jié)點(diǎn)為0，左右節(jié)點(diǎn)剪枝結(jié)果為null，不保留這個(gè)節(jié)點(diǎn)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if(root==null)return null;
        TreeNode newRoot;
        TreeNode left = pruneTree(root.left);
        TreeNode right = pruneTree(root.right);
        if(root.val==1){
            newRoot = new TreeNode(root.val);
            newRoot.left = left;
            newRoot.right= right;
        }else if(left!=null||right!=null){
            newRoot = new TreeNode(root.val);
            newRoot.left = left;
            newRoot.right= right;
        }else{
            newRoot=null;
        }
        return newRoot;
        
    }
}

二叉搜索樹

https://blog.csdn.net/qq_37887537/article/details/75647670

1.將有序數(shù)組轉(zhuǎn)化為二叉搜索樹

https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/description/
二叉搜索樹按照中序遍歷可得到有序數(shù)組；那么反之，我們可以得知，根節(jié)點(diǎn)是有序數(shù)組的中間節(jié)點(diǎn)，從中間節(jié)點(diǎn)分開左右兩個(gè)有序數(shù)組，這兩個(gè)有序數(shù)組的中間節(jié)點(diǎn)又分別為中間節(jié)點(diǎn)的左右子節(jié)點(diǎn)。這就是二分查找的中心思想啊。
思路：
用二分查找法，找到根節(jié)點(diǎn)，然后左子節(jié)點(diǎn)為左區(qū)間的中間節(jié)點(diǎn)；右子節(jié)點(diǎn)為右區(qū)間的中間節(jié)點(diǎn)。遞歸而成

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return midSortToBST(nums,0,nums.length-1);
    }
    private TreeNode midSortToBST(int[] nums,int left,int right){
        if(left>right)return null;
        int mid = (left+right)/2;
        TreeNode cur = new TreeNode(nums[mid]);
        cur.left = midSortToBST(nums,left,mid-1);
        cur.right = midSortToBST(nums,mid+1,right);
        return cur;
    }
}

2.二叉搜索樹剪枝

https://leetcode-cn.com/problems/trim-a-binary-search-tree/description/
二叉搜索樹不一定是平衡樹。
思路：
1.如果root值小于L，則拋棄左子樹，返回右子樹的剪枝結(jié)果
2.如果root值大于R，則拋棄右子樹，返回左子樹的剪枝結(jié)果
3.如果root值介于L與R之間，則根為root的值，左右節(jié)點(diǎn)分別是左右子樹的剪枝結(jié)果

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if(root==null)return null;
        if(root.val<L){
            return trimBST(root.right,L,R);
        }else if(root.val>R){
            return trimBST(root.left,L,R);
        }else{
            TreeNode cur = new TreeNode(root.val);
            cur.left = trimBST(root.left,L,R);
            cur.right = trimBST(root.right,L,R);
            return cur;
        }
    }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 樹的概述 樹是一種非常常用的數(shù)據(jù)結(jié)構(gòu)，樹與前面介紹的線性表，棧，隊(duì)列等線性結(jié)構(gòu)不同，樹是一種非線性結(jié)構(gòu) 1.樹的定...
    Jack921閱讀 4,757評(píng)論 1贊 31
  • 上一篇文章講述了樹的概念， 特征以及分類， 旨在讓我們理解什么是樹， 樹的一些常用的概念是什么，樹的分類有哪些等。...
    DevCW閱讀 2,226評(píng)論 4贊 10
  • //轉(zhuǎn)載請(qǐng)標(biāo)明出處，原文地址：http://blog.csdn.net/hackbuteer1/article/d...
    大海一滴寫字的地方閱讀 769評(píng)論 0贊 2
  • 一直以來(lái)，我都很少使用也避免使用到樹和圖,總覺得它們神秘而又復(fù)雜，但是樹在一些運(yùn)算和查找中也不可避免的要使用到，那...
    24K男閱讀 6,857評(píng)論 5贊 14
  • 什么是二叉樹？ 引用自百度百科：在計(jì)算機(jī)科學(xué)中，二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（...
    AnICoo1閱讀 1,471評(píng)論 0贊 1

友情鏈接更多精彩內(nèi)容