Leetcode#114Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List


 Total Accepted: 46999 Total Submissions: 163018My Submissions
Question Solution 
Given a binary tree, flatten it to a linked list in-place.
For example,Given
         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

click to show hints.
분석: 두 갈래 나무를 왼쪽 갈래 나무로 바꾸기
public class Solution {
    TreeNode H;
    void TravelTree(TreeNode x){
        H.right=x;
        H.left=null;
        H=H.right;
        
        TreeNode l=x.left;
        TreeNode r=x.right;
        x.left=null;
        x.right=null;
        if(l!=null)
            TravelTree(l);
        if(r!=null)
            TravelTree(r);
    }
    
    public void flatten(TreeNode root) {
        if(root!=null)
        {
            H=root;
            TreeNode l=root.left;
            TreeNode r=root.right;
            root.left=null;
            root.right=null;
            if(l!=null)
                TravelTree(l);
            if(r!=null)
                TravelTree(r);
        }
       /*
        Stack s1=new Stack();
        Stack s2=new Stack();
        
        if(root!=null)
        {
           //TreeNode head=new TreeNode(0);
            TreeNode h=root;
            if(root.left!=null)
                s1.push(root.left);
            if(root.right!=null)
                s1.push(root.right);
            while(!s1.isEmpty())
            {
                TreeNode p=s1.peek();
                s2.push(p);
                s1.pop();
                int mini=p.val;
                TreeNode minitn=p;
                while(!s1.isEmpty())
                {
                    p=s1.peek();
                    s2.push(p);
                    s1.pop();
                    if(p.val                    {
                        mini=p.val;
                        minitn=p;
                    }
                }
                
                while(!s2.isEmpty())
                {
                    p=s2.peek();
                    if(p==minitn)
                    {
                        h.right=p;
                        h.left=null;
                        h=h.right;
                        s2.pop();
                        if(p.left!=null)
                            s1.push(p.left);
                        if(p.right!=null)
                            s1.push(p.right);
                    }
                    else
                    {
                        s2.pop();
                        s1.push(p);
                    }
                }
                
            }
        }
        */
    }
}

좋은 웹페이지 즐겨찾기