劍指offer打卡|二叉搜索樹與雙向鏈表

標簽：劍指

題目描述

輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。

代碼

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.ArrayList;
public class Solution {
    //要求不能創建任何新的結點，只能在原本樹的結構中進行指針指向的調整
    //利用一個list來存放中序遍歷的樹
    private ArrayList<TreeNode> list=new ArrayList<>();
    public TreeNode Convert(TreeNode pRootOfTree) {
        MidOrder(pRootOfTree);
        if(list.size()==0||list.size()==1){
            return pRootOfTree;
        }
        TreeNode root=null;
        TreeNode pre=null;
        TreeNode next=null;
        for(int i=0;i<list.size()-1;i++){
            //arraylsit不能用[i]遍歷，只能用get、set
            if(i==0){
                //當前為鏈表的頭結點，其pre為null
                root=list.get(i);
                root.left=pre;
                pre=root;
                next=list.get(i+1);
                root.right=next;
            }else{
                next.left=pre;
                pre=next;
                next=list.get(i+1);
                pre.right=next;
            }
        }
        //當前為尾結點，其next為null
        next.right=null;
        next.left=pre;
        return root;
    }
    private void MidOrder(TreeNode node){
        if(node==null){
            return;
        }
        if(node.left!=null){
            MidOrder(node.left);
        }
        list.add(node);
        if(node.right!=null){
            MidOrder(node.right);
        }
    }
}

本文鏈接：https://blog.csdn.net/sinat_35738209/article/details/103931898

智能推薦

二叉搜索樹與雙向鏈表（劍指OFFER 面試題36）

題目描述輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。思路在二叉樹中，每個節點都有兩個指向子節點的指針。在雙向鏈表中，每個節點也有兩個指針，分別一個指向前一個指向后。由于這兩種結構相似，同時二叉搜索樹也是一中排序的數據結構，因此，理論上可以實現搜索二叉樹和雙向鏈表的轉換。在搜索二叉樹中，左子節點的值總是小于父節點的值，右子...

劍指offer-二叉搜索樹與雙向鏈表

題目描述輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。思路：這道題真沒想到該怎么做，思路比較混亂看完CYC大神的才會做...

劍指offer 二叉搜索樹與雙向鏈表

1.題目輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。來源：劍指offer 鏈接：https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&rp=1&ru=/ta/coding-interv...

《劍指Offer》36. 二叉搜索樹與雙向鏈表

題目鏈接牛客網題目描述輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。解題思路...

36劍指offer 二叉搜索樹與雙向鏈表

題目描述輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。由于要求轉換成一個排序的雙向鏈表，因為二叉搜索樹的中序遍歷就是有序的，因此遍歷過程中可以使用中序遍歷。分析與解法：首先我們知道：在二叉樹中，每個結點都有兩個指向子結點的指針。在雙向鏈表中，每個結點也有兩個指針，它們分別指向前一個結點和后一個結點。...