改变tree的结构

2016-12-10 Bobst

• 维护一个prev node
• 观察以什么order来traversal

Flatten Binary Tree to Linked List

         1
        / \
       2   5
      / \   \
     3   4   6


       1
        \
         2
          \
           3
            \
             4
              \
               5
                \
                 6

这题的本质是什么？

pre-order + 维护prev节点

public void flatten(TreeNode root) {
    List<TreeNode> prev = new ArrayList<>();
    prev.add(null);
    dfs(root, prev);
}

public void dfs(TreeNode root, List<TreeNode> prev) {
    if(root == null) {
        return;
    }

    // pre-order
    if(prev.get(0) != null) {
        prev.get(0).left = null;
        prev.get(0).right = root;
    }

    prev.set(0, root);

    TreeNode right = root.right;
    // 因为改变的是前置节点的右孩子
    dfs(root.left, prev);
    dfs(right, prev);
}

Binary Tree Upside Down

        1
       / \
      2   3
     / \
    4   5
        ||
        \/
       4
      / \
     5   2
        / \
       3   1

其实就是把一个节点的左孩子变成变成父节点，右孩子变成左孩子的左孩子。

是一个类似于in-order

递归版做法：

public TreeNode upsideDownBinaryTree(TreeNode root) {
    // 从最左节点的父节点开始处理
    if(root == null || root.left == null) {
        return root;
    }

    // cache了往左那条path上的所有节点
    TreeNode newRoot = upsideDownBinaryTree(root.left);

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

    return newRoot;
}

迭代：

顺着最左边的一条path 走下去就可以了

public TreeNode upsideDownBinaryTree(TreeNode root) {
    TreeNode curr = root;
    TreeNode prev = null, temp = null;

    while(curr != null) {
        TreeNode next = curr.left;
        curr.left = temp;
        temp = curr.right;
        curr.right = prev;

        prev = curr;
        curr = next;
    }

    return prev;
}

BST to doubly linked list （FB）

in - order 的递归结构，左-中-右

核心在于 “中” 这步上，如何正确做好 “拼接” 工作

我们需要存一个全局变量 prev 用于保存 "左子树的最后一个节点"，在每步上，和 root 做双向拼接； prev 初始化为 null;

额外用于遍历 LinkedList 还需要存下 head ; 在 prev 为 null 的时候 root 就代表着最左面的节点，设一下就好，之后就不用管了。

时间复杂度O(n)

static TreeNode prev = null;
static TreeNode head;

public static void convert(TreeNode root) {
    if(root == null) return;

    // in-order
    convert(root.left);

    // reach the most-left node
    if(prev == null) {
        head = root;
    } else {
        root.left = prev;
        prev.right = root;
    }

    prev = root;

    convert(root.right);
}

迭代的做法

因为是in-order, 所以用stack来做，其他基本和递归是一样的，用prev node和当前的节点进行拼接，然后更新prev node

public TreeNode convert(TreeNode root) {
    if(root == null) {
        return null;
    }

    LinkedList<TreeNode> stack = new LinkedList<>();
    TreeNode prev = null, head = null;

    TreeNode cur = root;

    while(!stack.isEmpty() || cur != null) {
        while(cur.left != null) {
            stack.push(cur.left);
            cur = cur.left;
        }

        TreeNode node = stack.pop();

        if(prev == null) {
            head = node;
        } else {
            node.prev = prev;
            prev.next = node;
        }

        prev = node;
        if(node.right != null) {
            cur = node.right;
        }
    }

    return head;
}