LeetCode : 114. Flatten Binary Tree to Linked List 将二叉树转成链表

Love The Way You Lie 2021-06-24 16:11 250阅读 0赞

**试题**  
Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

1
       / \
      2   5
     / \   \
    3   4   6

The flattened tree should look like:

1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6

**代码**  
先序遍历是将前一个节点地址记录下来。不过这里边有个注意点就是：你在处理当前节点时会导致上一个节点的left和next值发生变化，需要用tmp变量存一下。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        TreeNode pre = new TreeNode(0);
        TreeNode head = pre;
        public void flatten(TreeNode root) {
            if(root==null) return;
            preOrder(root);
            root = head.right;
        }
        
        public void preOrder(TreeNode root){
            if(root==null) return;
            TreeNode tmpRight = root.right;
            TreeNode tmpLeft = root.left;
            
            pre.left = null;
            pre.right = root;
            pre = root;
            
            preOrder(tmpLeft);
            preOrder(tmpRight);        
        }
    }

private TreeNode prev = null;
    
    public void flatten(TreeNode root) {
        if (root == null)
            return;
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }