[Sword Pointing OFFER] Tree JZ36 Binary Search Tree and Doubly Linked List

Article directory

1. Topic

Input a [binary search tree] , convert the binary search tree into a sorted doubly linked list.

2. Solution

2.1 The structure of the tree

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

2.2 Solution 1

The characteristic of a binary search tree is that the left is small and the right is large.
Consider, the return should be the leftmost child of this tree. i.e. the minimum value.
So find the node first.
And use in-order traversal to sort out the relationship.
Save the left subtree, the most recently visited value, through pre.

public  class  Solution {
     public TreeNode Convert ( TreeNode pRootOfTree ) {
         if (pRootOfTree== null ) return  null ;
        TreeNode left = pRootOfTree;
        while (left.left!=null){
            left = left.left;
        }
        helper(pRootOfTree);
        return left;
    }

    TreeNode pre = null;
    public void helper(TreeNode root) {
        if (root == null) return ;
        helper(root.left);
        root.left = pre;
        if(pre!=null) pre.right = root;
        pre = root;
        helper(root.right);
    }
}

Summarize

Consider, the return should be the leftmost child of this tree. i.e. the minimum value.

The algorithm series has an open source project on github, mainly the demo code of this series of blogs. [https://github.com/forestnlp/alg]
If you are interested in software development, machine learning, and deep learning, please pay attention to this blog, and will continue to launch Java, software architecture, and deep learning related columns.
Your support is my greatest encouragement.

Leave a Comment

Your email address will not be published. Required fields are marked *