Flatten Binary Tree to Linked List | LeetCode | Java

Approach 1 : Using DFS

<span>class</span> <span>Solution</span> <span>{</span>
    <span>TreeNode</span> <span>prevNode</span> <span>=</span> <span>null</span><span>;</span>
    <span>public</span> <span>void</span> <span>flatten</span><span>(</span><span>TreeNode</span> <span>root</span><span>)</span> <span>{</span>
        <span>if</span><span>(</span><span>root</span><span>==</span><span>null</span><span>)</span>
            <span>return</span><span>;</span>
        <span>flatten</span><span>(</span><span>root</span><span>.</span><span>right</span><span>);</span>
        <span>flatten</span><span>(</span><span>root</span><span>.</span><span>left</span><span>);</span>
        <span>root</span><span>.</span><span>right</span> <span>=</span> <span>prevNode</span><span>;</span>
        <span>root</span><span>.</span><span>left</span> <span>=</span> <span>null</span><span>;</span>
        <span>prevNode</span> <span>=</span> <span>root</span><span>;</span>
    <span>}</span>
<span>}</span>
<span>class</span> <span>Solution</span> <span>{</span>
    <span>TreeNode</span> <span>prevNode</span> <span>=</span> <span>null</span><span>;</span>
    <span>public</span> <span>void</span> <span>flatten</span><span>(</span><span>TreeNode</span> <span>root</span><span>)</span> <span>{</span>

        <span>if</span><span>(</span><span>root</span><span>==</span><span>null</span><span>)</span>
            <span>return</span><span>;</span>

        <span>flatten</span><span>(</span><span>root</span><span>.</span><span>right</span><span>);</span>
        <span>flatten</span><span>(</span><span>root</span><span>.</span><span>left</span><span>);</span>
        <span>root</span><span>.</span><span>right</span> <span>=</span> <span>prevNode</span><span>;</span>
        <span>root</span><span>.</span><span>left</span> <span>=</span> <span>null</span><span>;</span>
        <span>prevNode</span> <span>=</span> <span>root</span><span>;</span>
    <span>}</span>
<span>}</span>
class Solution {
    TreeNode prevNode = null;
    public void flatten(TreeNode root) {

        if(root==null)
            return;

        flatten(root.right);
        flatten(root.left);
        root.right = prevNode;
        root.left = null;
        prevNode = root;
    }
}

Enter fullscreen mode Exit fullscreen mode

Approach 2 : Using Stack (BFS)

<span>class</span> <span>Solution</span> <span>{</span>
    <span>public</span> <span>void</span> <span>flatten</span><span>(</span><span>TreeNode</span> <span>root</span><span>)</span> <span>{</span>
        <span>if</span><span>(</span><span>root</span><span>==</span><span>null</span><span>)</span>
            <span>return</span><span>;</span>
        <span>Stack</span><span><</span><span>TreeNode</span><span>></span> <span>stack</span> <span>=</span> <span>new</span> <span>Stack</span><span><>();</span>
        <span>stack</span><span>.</span><span>add</span><span>(</span><span>root</span><span>);</span>
        <span>while</span><span>(!</span><span>stack</span><span>.</span><span>isEmpty</span><span>()){</span>
                <span>TreeNode</span> <span>currentNode</span> <span>=</span> <span>stack</span><span>.</span><span>pop</span><span>();</span>
                <span>if</span><span>(</span><span>currentNode</span><span>.</span><span>right</span><span>!=</span><span>null</span><span>)</span>
                    <span>stack</span><span>.</span><span>push</span><span>(</span><span>currentNode</span><span>.</span><span>right</span><span>);</span>
                <span>if</span><span>(</span><span>currentNode</span><span>.</span><span>left</span><span>!=</span><span>null</span><span>)</span>
                    <span>stack</span><span>.</span><span>push</span><span>(</span><span>currentNode</span><span>.</span><span>left</span><span>);</span>
                <span>if</span><span>(!</span><span>stack</span><span>.</span><span>isEmpty</span><span>())</span>
                    <span>currentNode</span><span>.</span><span>right</span> <span>=</span> <span>stack</span><span>.</span><span>peek</span><span>();</span>
                <span>currentNode</span><span>.</span><span>left</span> <span>=</span> <span>null</span><span>;</span>
        <span>}</span>
    <span>}</span>
<span>}</span>
<span>class</span> <span>Solution</span> <span>{</span>
    <span>public</span> <span>void</span> <span>flatten</span><span>(</span><span>TreeNode</span> <span>root</span><span>)</span> <span>{</span>

        <span>if</span><span>(</span><span>root</span><span>==</span><span>null</span><span>)</span>
            <span>return</span><span>;</span>

        <span>Stack</span><span><</span><span>TreeNode</span><span>></span> <span>stack</span> <span>=</span> <span>new</span> <span>Stack</span><span><>();</span>

        <span>stack</span><span>.</span><span>add</span><span>(</span><span>root</span><span>);</span>

        <span>while</span><span>(!</span><span>stack</span><span>.</span><span>isEmpty</span><span>()){</span>

                <span>TreeNode</span> <span>currentNode</span> <span>=</span> <span>stack</span><span>.</span><span>pop</span><span>();</span>

                <span>if</span><span>(</span><span>currentNode</span><span>.</span><span>right</span><span>!=</span><span>null</span><span>)</span>
                    <span>stack</span><span>.</span><span>push</span><span>(</span><span>currentNode</span><span>.</span><span>right</span><span>);</span>

                <span>if</span><span>(</span><span>currentNode</span><span>.</span><span>left</span><span>!=</span><span>null</span><span>)</span>
                    <span>stack</span><span>.</span><span>push</span><span>(</span><span>currentNode</span><span>.</span><span>left</span><span>);</span>

                <span>if</span><span>(!</span><span>stack</span><span>.</span><span>isEmpty</span><span>())</span>
                    <span>currentNode</span><span>.</span><span>right</span> <span>=</span> <span>stack</span><span>.</span><span>peek</span><span>();</span>

                <span>currentNode</span><span>.</span><span>left</span> <span>=</span> <span>null</span><span>;</span>
        <span>}</span>
    <span>}</span>
<span>}</span>
class Solution {
    public void flatten(TreeNode root) {

        if(root==null)
            return;

        Stack<TreeNode> stack = new Stack<>();

        stack.add(root);

        while(!stack.isEmpty()){

                TreeNode currentNode = stack.pop();

                if(currentNode.right!=null)
                    stack.push(currentNode.right);

                if(currentNode.left!=null)
                    stack.push(currentNode.left);

                if(!stack.isEmpty())
                    currentNode.right = stack.peek();

                currentNode.left = null;
        }
    }
}

Enter fullscreen mode Exit fullscreen mode

Thanks for reading 🙂
Feel free to comment and like the post if you found it helpful
Follow for more 🤝 && Happy Coding

If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7

原文链接：Flatten Binary Tree to Linked List | LeetCode | Java