0001年1月1日

Ŀ

һööתһ˫ҪܴκµĽ㣬ֻܵнָָ

##

##

˫

##Ŀ

ڵ

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

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

    }

}

ӢBinary Search TreeҲƶӢordered binary treeӢsorted binary treeָһÿ߾ʵĶ

ⷨһݹ飩ʱ䣺32msռڴ棺550k

//ݹ    
public class Solution {
     //˫ͷұͷڵ
    TreeNode leftHead = null;
    TreeNode rightHead = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
         //ݹҶӽڵҽڵ㷵null
        if(pRootOfTree==null) return null;
         //һʱʹҶӽڵΪһڵ
        Convert(pRootOfTree.left);
        if(rightHead==null){
            leftHead= rightHead = pRootOfTree;
        }else{
            //Ѹڵ뵽˫ұߣrightHeadƶ
           rightHead.right = pRootOfTree;
           pRootOfTree.left = rightHead;
           rightHead = pRootOfTree;
        }
         //ҶӽڵҲ뵽˫rightHeadȷֱӲ룩
        Convert(pRootOfTree.right);
         //ͷ
        return leftHead;
    }
}

ҵߵҶӽڵ㣬ԸýڵΪ˫ĵһڵ㣬Ȼݡ󡡸ҡΰѽڵ뵽˫ұ߲ƶrightHeadָ 󷵻leftHead

ⷨʱ䣺31msռڴ棺503k

import java.util.Stack;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return pRootOfTree;
        //˫ͷұͷڵ
        TreeNode leftHead = null;
        TreeNode rightHead = null;
       Stack<TreeNode> s = new Stack<TreeNode>();
       while(pRootOfTree != null || !s.isEmpty()){
            if(pRootOfTree != null) {
                //αҶڵ
                s.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            } else {
                pRootOfTree = s.pop();
                if(rightHead == null)
                    //ҶӽڵΪͷ
                    leftHead = rightHead = pRootOfTree;
                else {
                    rightHead.right = pRootOfTree;
                    pRootOfTree.left = rightHead;
                    rightHead = pRootOfTree;
                }
                pRootOfTree = pRootOfTree.right;
            }
        }
         
        return leftHead;
    }
}

˼·һҶӽڵΪͷöջ