首页 > 代码库 > leetcode--Flatten Binary Tree to Linked List

leetcode--Flatten Binary Tree to Linked List

2024-07-08 00:32:25   220人阅读

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

For example,
Given

         1
        /        2   5
      / \        3   4   6

 

The flattened tree should look like:

   1
         2
             3
                 4
                     5
                         6

click to show hints.

method 1 recursive method:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
 
    public void flatten(TreeNode root) {
        if(root != null){
            TreeNode aNode = root.left;
            if(aNode != null){
                while(aNode.right != null)
                    aNode = aNode.right;
                aNode.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            root = root.right;
            flatten(root);
        }   
    }
}

　　

method2: preorder tree traversal method

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public void flatten(TreeNode root) {
        Stack<TreeNode> nodes = new Stack<TreeNode>();
        if(root != null){
            TreeNode currentNode = root;
            if(root.right != null)
                nodes.push(root.right);
            if(root.left != null){
                nodes.push(root.left);
                root.left = null;
            }
            while(!nodes.isEmpty()){
                TreeNode aNode = nodes.pop();
                currentNode.right = aNode;
                //currentNode.left = null;
                currentNode = currentNode.right;
                if(aNode.right != null)
                    nodes.push(aNode.right);
                if(aNode.left != null){
                    nodes.push(aNode.left);
                    aNode.left = null;
                }
            }
        }
    }
}

　　


联系
我们