樹(shù)（簡(jiǎn)單）

二叉樹(shù)的前序遍歷

  • @遞歸

public static void preOrderRecur(TreeNode head) {
        if (head == null) {
            return;
        }
        preOrderRecur(head.left);
        System.out.print(head.val + " ");
        preOrderRecur(head.right);
    }

  • @迭代

public static void preOrderIteration(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

二叉樹(shù)的中序遍歷

  • @遞歸

public static void preOrderRecur(TreeNode head) {
        if (head == null) {
            return;
        }
        System.out.print(head.val + " ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }

  • @迭代

public static void inOrderIteration(TreeNode head) {
            if (head == null) {
                return;
            }
            TreeNode cur = head;
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || cur != null) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                TreeNode node = stack.pop();
                System.out.print(node.val + " ");
                if (node.right != null) {
                    cur = node.right;
                }
            }
        }

二叉樹(shù)的后序遍歷

  • @遞歸

public static void postOrderRecur(TreeNode head) {
        if (head == null) {
            return;
        }
        postOrderRecur(head.left);
        postOrderRecur(head.right);
        System.out.print(head.val + " ");
    }

  • @迭代

/*迭代寫(xiě)法，利用pre記錄上一個(gè)訪問(wèn)過(guò)的結(jié)點(diǎn)，與當(dāng)前結(jié)點(diǎn)比較，
    如果是當(dāng)前結(jié)點(diǎn)的子節(jié)點(diǎn)，說(shuō)明其左右結(jié)點(diǎn)均已訪問(wèn)，將當(dāng)前結(jié)點(diǎn)出棧，
    更新pre記錄的對(duì)象。 寫(xiě)法(3)：取巧的方法。該寫(xiě)法的訪問(wèn)順序并不是后序遍歷，
    而是利用先序遍歷“根左右”的遍歷順序，
    將先序遍歷順序更改為“根右左”，反轉(zhuǎn)結(jié)果List，得到結(jié)果順序?yàn)椤白笥腋?/
    public List<Integer> postorderTraversal(TreeNode root) {//非遞歸寫(xiě)法
        List<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode pre = null;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode curr = stack.peek();
            if((curr.left == null && curr.right == null) ||
                    (pre != null && (pre == curr.left || pre == curr.right))){
                //如果當(dāng)前結(jié)點(diǎn)左右子節(jié)點(diǎn)為空或上一個(gè)訪問(wèn)的結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)的子節(jié)點(diǎn)時(shí)，當(dāng)前結(jié)點(diǎn)出棧
                res.add(curr.val);
                pre = curr;
                stack.pop();
            }else{
                if(curr.right != null) stack.push(curr.right); //先將右結(jié)點(diǎn)壓棧
                if(curr.left != null) stack.push(curr.left);   //再將左結(jié)點(diǎn)入棧
            }
        }
        return res;
    }
/*
//方法(3)
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node.left != null) stack.push(node.left);//和傳統(tǒng)先序遍歷不一樣，先將左結(jié)點(diǎn)入棧
            if(node.right != null) stack.push(node.right);//后將右結(jié)點(diǎn)入棧
            res.add(0,node.val);                        //逆序添加結(jié)點(diǎn)值
        }
        return res;
}

從上到下打印二叉樹(shù)

public int[] levelOrder(TreeNode root) {
        Queue<TreeNode> q=new LinkedList<>();
        List<Integer> res=new ArrayList<>();
        if(root==null)
            return new int[]{};
        q.add(root);
        while(!q.isEmpty())
        {
            TreeNode temp=q.poll();
            res.add(temp.val);
            if(temp.left!=null)
                q.add(temp.left);
            if(temp.right!=null)
                q.add(temp.right);
        }
        int[] resf=new int[res.size()];
        for(int i=0;i<res.size();i++)
        {
            resf[i]=res.get(i);
        }
        return resf;
    }

從上到下打印二叉樹(shù)II

 public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null)
            return null;
        List<List<Integer>> res=new ArrayList();
        Queue<TreeNode> q=new LinkedList();
        q.add(root);
        while(!q.isEmpty())
        {
            List<Integer>tem=new ArrayList();
            for(int i=q.size();i>0;i--)
            {
                TreeNode no=q.poll();
                tem.add(no.val);
                if(no.left!=null) q.add(no.left);
                if(no.right!=null) q.add(no.right);

            }
            res.add(tem);
        }
        return res;
    }

二叉樹(shù)的深度

  • @迭代

public int getTreeHeight(TreeNode root){
       if(null==root){
           return 0;
       }
       ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
       int height=0;
       queue.add(root);
       while(!queue.isEmpty()){
           int size=queue.size();
           for(int i=0;i<size;i++){
               TreeNode node=queue.removeFirst();
               if(null!=node.left){
                   queue.add(node.left);
               }
               if(null!=node.right){
                   queue.add(node.right);
               }
           }
           height++;
       }
       return height;
   }

  • @遞歸

 public int maxDepth1(TreeNode root)
    {
        if(root==null)
        {
            return 0;
        }
        int leftLen=maxDepth1(root.right);
        int rightLen=maxDepth1(root.left);
        return Math.max(leftLen,rightLen)+1;
    }
image.png

  • @遞歸一

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //根節(jié)點(diǎn)到p節(jié)點(diǎn)的路徑
        List<TreeNode> path1 = new ArrayList<>();
        //根節(jié)點(diǎn)到q節(jié)點(diǎn)的路徑
        List<TreeNode> path2 = new ArrayList<>();
        getPath(root,p,path1);
        getPath(root,q,path2);

        TreeNode result=null;
        int n = Math.min(path1.size(),path2.size());
        //保留最后一個(gè)相等的節(jié)點(diǎn)即為公共節(jié)點(diǎn)
        for(int i=0;i<n;i++){
            if(path1.get(i)==path2.get(i))
                result = path1.get(i);
        }
        return result;
    }
    //前序遍歷搜索節(jié)點(diǎn)p或q
    void getPath(TreeNode root,TreeNode node,List<TreeNode> path){
        if(root==null)
            return ;
        path.add(root);
        if(root == node)
            return ;
        if(path.get(path.size()-1)!=node){
            getPath(root.left,node,path);
        }
        if(path.get(path.size()-1)!=node){
            getPath(root.right,node,path);
        }
        if(path.get(path.size()-1)!=node){
            path.remove(path.size()-1);
        }
    }

  • @遞歸二

/*
如果root是null，則說(shuō)明我們已經(jīng)找到最底了，返回null表示沒(méi)找到
如果root與p相等或者與q相等，則返回root
如果左子樹(shù)沒(méi)找到，遞歸函數(shù)返回null，證明p和q同在root的右側(cè)，
那么最終的公共祖先就是右子樹(shù)找到的結(jié)點(diǎn)
如果右子樹(shù)沒(méi)找到，遞歸函數(shù)返回null，證明p和q同在root的左側(cè)，
那么最終的公共祖先就是左子樹(shù)找到的結(jié)點(diǎn)
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root==p || root==q)
            return root;
        TreeNode leftNode=lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode=lowestCommonAncestor(root.right,p,q);
        if(leftNode==null)
            return rightNode;
        if(rightNode==null)
            return leftNode;
        return root;
    }

  • @迭代一

 public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root.val==p.val||root.val==q.val)
        {
            return root;
        }
        HashMap<TreeNode, TreeNode> fathers = new HashMap<>();
        get_fathers1(fathers,root);
        ArrayList<TreeNode> p_path=get_path1(fathers,p);
        ArrayList<TreeNode> q_path =get_path1(fathers,q);
        return common_tail1(p_path,q_path);

    }
    public void get_fathers1(HashMap fathersMap,TreeNode root){
        Stack<TreeNode> fatherStack = new Stack<>();
        fatherStack.push(root);
        fathersMap.put(root,null);
        while (!fatherStack.isEmpty())
        {
            TreeNode temp=fatherStack.pop();
            if(temp.right!=null)
            {
                fatherStack.push(temp.right);
                fathersMap.put(temp.right,temp);
            }
            if(temp.left!=null)
            {
                fatherStack.push(temp.left);
                fathersMap.put(temp.left,temp);
            }
        }
    }
    public ArrayList<TreeNode> get_path1(HashMap<TreeNode,TreeNode> fathersMap,TreeNode target)
    {
        ArrayList<TreeNode> path = new ArrayList<>();
        path.add(target);
        while(fathersMap.get(target)!=null)
        {

            path.add(fathersMap.get(target));
            target=fathersMap.get(target);
        }
        return path;
    }
    public TreeNode common_tail1(ArrayList<TreeNode> p_path,ArrayList<TreeNode> q_path)
    {
        int p=p_path.size()-1,q=q_path.size()-1;
        while (p>=0&&q>=0&&p_path.get(p).val==q_path.get(q).val)
        {
            p--;
            q--;
        }
        return p_path.get(p+1);
    }

平衡二叉樹(shù)

/*先序遍歷*/
    public boolean isBalanced(TreeNode root) {
        if(root==null)
        {
            return true;
        }
        int lefthieght=gettreehieght(root.left);
        int rightHieght=gettreehieght(root.right);
        if(Math.abs(lefthieght-rightHieght)>1)
        {
            return false;
        }
        else {
            return isBalanced(root.left)&&isBalanced(root.right);
        }
    }
    public int gettreehieght( TreeNode root)
    {
        if(root==null)
        {
            return 0;
        }
        else
            return Math.max(gettreehieght(root.left),gettreehieght(root.right))+1;
    }

路徑總和

int pathNumber=0;
    public int pathSum(TreeNode root, int sum) {
        if(root==null)
            return 0;
        Sum(root,sum);
        pathSum(root.left,sum);
        pathSum(root.right,sum);
        return pathNumber;
    }
    private void Sum(TreeNode root, int sum) {
        if(root==null)
            return;
        sum-=root.val;
        if(sum==0)
        {
            pathNumber++;
        }
        Sum(root.right,sum);
        Sum(root.left,sum);
    }
?著作權(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)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

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

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