[leetcode]114. Flatten Binary Tree to Linked List

タイトルリンク:114.Flatten Binary Tree to Linked List Given a binary tree, flatten it to a linked list in-place. Hints: If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.
この問題について,その二叉木がプログラミングしたチェーンテーブルの各ノードのサブノードが,このツリーを先にそのノードの次のノードを遍歴することであることが分かった.だからこの問題の構想もきっと先序遍歴と関係があるに違いない.(二叉木の遍歴).二叉木の先序遍歴のアルゴリズムによれば,最も左寄りの列のサブノードは,先序遍歴で最初にアクセスされたノード,すなわち,この問題が生成するチェーンテーブルの中で最も前寄りのノードであることが分かった.したがって,右にチェーンテーブルを生成する必要がある場合は,まず左右のサブツリーを交換して再帰する過程が必要であり,最も左寄りのノードの列が正しい位置に置かれる.元のテーマで要求された右構造のチェーンテーブルのほか、左構造のチェーンテーブルのコードも補足しました.
具体的な考え方はコードと注釈を見てください.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        flattenfunction(root);
    }

    /*
    This method flattens a binary tree and constructs it into a linked list in the right subtree
    @param current root used for the flatten function
    @return the tree node that is the last one in the right subtree
    */
    private TreeNode flattenfunction(TreeNode root){
        if (root == null){
            return root;
        }
        if (root.left != null){
            //since we have to construct the binary tree in the order of pre-order traversal and we know that the left most nodes in the tree are always the nodes that are visited firstly (as the pre-order traversal algorithm like), so we just switch the left subtree of every level in the left subtree of the original root into the right side and recurse this process.
            //after this process, we have move every left most nodes into the right place of the linked list 
            //switch left and right subtree
            TreeNode temp = root.right;
            root.right = root.left;
            root.left = temp;
        }
        if (root.right != null){
            //While there are nodes in the right subtree(after switch), we'll recurse the process with the right child as the root parameter. //While there is no left child on this node, we can return the last node safely because without left subtree there can't be any nodes that can be switched to right subtree which make the right subtree deeper
            //If there still is left subtree, we switch it to the right subtree of the last node and recurse the process. At the same time, we let the left subtree of the root to be null
            //Node last stores the last node in the right subtree
            TreeNode last = flattenfunction(root.right);
            if (root.left == null){
                return last;
            }

            last.right = root.left;
            root.left = null;

            return flattenfunction(last.right);
        }
        //if both left and right are null, then current root should be the last one.
        return root;
    }

    /*
    this method returns a linked list that is constructed on the left subtree of every node.
    */
    private TreeNode leftflatten(TreeNode root){
        if (root == null){
            return root;
        }
        if (root.left != null){
            //we return the last node by recursion
            TreeNode last = leftflatten(root.left);
            if (root.right != null){
                //if there still exists a right subtree, we make it to be the left child of the last node and make the right child of the to be null
                last.left = root.right;
                root.right = null;
                return leftflatten(last.left);
            }
            else {
                return last;
            }
        }
        if (root.right != null ){
            //while root.left == null and root.right != null, we just switch the right subtree to the left subtree and execute the process.
            root.left = root.right;
            root.right = null;
            return leftflatten(root.left);
        }

        //while both left and right child of the root is null, we know it should be the leaf node(last node) and return it
        return root;
    }
}