114. Flatten Binary Tree to Linked List

Question

Given the root of a binary tree, flatten the tree into a “linked list”:

• The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
• The “linked list” should be in the same order as a pre-order** traversal** of the binary tree.

Solution

全局变量prev，初始化为null，用来记录上一个访问的节点。

由于最后要达到先序遍历（根节点-左子节点-右子节点）的数据结构顺序，因此在进行访问时需要与先序遍历的操作相反，首先递归右子节点，然后递归左子节点，最后修改当前节点。

先遍历当前节点的右侧节点，再遍历当前节点的左侧节点。
最后处理当前节点，将左子节点设置为null，右子节点设置为prev。
最后将当前节点保存在prev上。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode prev = null;
    public void flatten(TreeNode root) {
        if(root == null) return;
        flatten(root.right);    //traverse right nodes first
        flatten(root.left); //traverse left nodes
        root.left = null;   //set current node's left child node to null
        root.right = prev;  //set current node's right child node to previous node
        prev = root;    //update previous node
    }
}