利口114 这个解法的复杂度是 n^2 吗

Job Hunting Interview
1

请大家帮忙分析分析？

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            flatten(root.left);
        }
        if (root.right != null) {
            flatten(root.right);
        }
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = null;
        while (root != null && root.right != null) {
            root = root.right;
        }
        root.right = tmp;
    }
}
2

贴下题目

WX20190325-133623_2x.png700×1126 40.2 KB

每个node只访问了一次， 应该是O(n)

3

x老师说的对，应该是On不是On2

4

应该是O(n), 每个node只被遍历了一次，楼主可能误解了recursion就是O(n^2)

5

老师，但是这个while loop，在找这个左子树最后面的node的时候，可能会比较耗时，导致每个node不止访问一次。如果是链表形式的tree，那就导致while loop每次都要用 ~ O(n)的时间找到末端的node，然后左右两端相连。

6

我主要是关心这个while loop找原左子树末端的复杂度比较高。

7

那你为何要去研究一个次优的解法？这题如下就可以了吧

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

我只是看到这个解法，忽然发现不太会分析复杂度，就学习学习。

9

还是找个最优解去分析 runtime，没必要花时间在次优解上

10

我也喜欢这解法

11

这个解法比较容易理解。