Tree-Medium

2020-02-26

Abstract： 更新部分Medium难度 Tree相关题解

94. Binary Tree Inorder Traversal

解法一：递归法

没什么好说的，不会砍手

class Solution {
    List<Integer> inorder=new ArrayList<Integer>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root!=null){
        inorder=inorderTraversal(root.left);
        inorder.add(root.val);
        inorder=inorderTraversal(root.right);}
        
        return inorder;
    }
}

解法二：迭代法

比递归法难理解一些，重点是理解好如何回溯

class Solution {
    List<Integer> inorder=new ArrayList<Integer>();
    Stack<TreeNode> stack=new Stack<TreeNode>();
    public List<Integer> inorderTraversal(TreeNode root) {
        TreeNode curr=root; //辅助接点curr，指向当前访问的TreeNode
        while(curr!=null || !stack.isEmpty()){ //当前访问的节点不为空或栈不为空，说明还没遍历完
            while(curr!=null){ //不断压入左节点
                stack.push(curr);
                curr=curr.left;
            }
            curr=stack.pop(); //**回溯**
            inorder.add(curr.val); //将当前访问的节点加入
            curr=curr.right; //如果有右节点则访问右节点，如果没有将在下一轮回溯或者结束
        }
        return inorder;
    }
}

解法三：莫比斯遍历

//待补全

96. Unique Binary Search Trees

解法一：递归法

**思路：**分别以1-n的任意整数为根，那么左右子树有哪些值是可以确定的，因此可以递归地来做
要点：{4,5,6,7,8}在此处可以等价于{1,2,3,4,5}，因此可以很方便的进行递归，但是在这里只是个取巧的做法
**缺点：**没有保存递归结果，增加了许多重复的操作，下一个解法考虑对结果进行缓存

class Solution {
    public int numTrees(int n) {
        if(n<=1)return 1; //特殊情况，以及递归的基准
        int uniqueNum=0;
        for(int i=1;i<=n;i++){uniqueNum+=numTrees(i-1)*numTrees(n-i);} //递归左右区间的乘积
        return uniqueNum;
    }
}

解法二：记忆化递归

直接递归的缺点是重复递归很多地方，所以需要剪枝

class Solution {
    public int numTrees(int n) {
        int[] dp=new int[n+1];
        return dynamicNumTrees(n,dp);
    }

    public int dynamicNumTrees(int n,int[] dp){
        if(n<=1){return 1;}
        if(dp[n]!=0){return dp[n];} //加入缓存
        for(int i=1;i<=n;i++){dp[n]+=dynamicNumTrees(i-1,dp)*dynamicNumTrees(n-i,dp);}
        return dp[n];
    }
}

95. Unique Binary Search Trees II

解法一：递归法

和上题类似的递归思路，不过注意root的创建时机

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n==0)return new LinkedList<TreeNode>(); //特殊情况
        return generate(1,n);
    }

    public List<TreeNode> generate(int lo,int hi){
        List<TreeNode> BSTs=new LinkedList<TreeNode>();     //注意ArrayList不能加入null
        if(lo>hi){BSTs.add(null);return BSTs;}              //加入null
        if(lo==hi){BSTs.add(new TreeNode(lo));return BSTs;} //递归边界
        for(int i=lo;i<=hi;i++){
            List<TreeNode> leftList=generate(lo,i-1);
            List<TreeNode> rightList=generate(i+1,hi); //分别取得左右子树的递归结果
            for(TreeNode leftRoot:leftList){
                for(TreeNode rightRoot:rightList){    
                    TreeNode root=new TreeNode(i);//root应该在循环体内new，否则会和上一轮的混淆
                    root.left=leftRoot;
                    root.right=rightRoot;
                    BSTs.add(root);
                }
            }
        }
        return BSTs;
    }
}

解法二：记忆化递归

//这是啥?

105. Construct Binary Tree from Preorder and Inorder Traversal

解法一：递归法

这题的重点是如何分别在inorder和preorder中划分左右子树

preorder的头部是root
**inorder如何划分：**在inorder中找到root，那么在此之前的为left，之后的为right
**preorder如何划分：**inorder中，left-root即为left的长度leftSize，由此推出以下关系

//左子树
next_p_lo=p_lo+1;
next_p_hi=p_lo+leftSize;
next_i_lo=i_lo;
next_i_hi=i_lo+leftSize+1;
//右子树
next_p_lo=p_lo+leftSize+1;
next_p_hi=p_hi;
next_i_lo=i_lo+leftSize+1;
next_i_hi=p_hi;

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len=preorder.length-1;
        return build(preorder,inorder,0,len,0,len);
    }

    public TreeNode build(int[] preorder,int[] inorder,int p_lo,int p_hi,int i_lo,int i_hi){
        if(p_lo>p_hi || i_lo>i_hi){return null;} //越界判定 & 递归结束
        int leftSize=0;
        for(int i=i_lo;i<=i_hi;i++){ //在inorder中找到root并算出leftSize
            if(inorder[i]==preorder[p_lo]){leftSize=i-i_lo;}
        }
        TreeNode root=new TreeNode(preorder[p_lo]); //依据已有关系，构造根节点和左右子树
        root.left=build(preorder,inorder,p_lo+1,p_lo+leftSize,i_lo,i_lo+leftSize-1);
        root.right=build(preorder,inorder,p_lo+leftSize+1,p_hi,i_lo+leftSize+1,i_hi);
        return root;
    }
}

新写法，忘了上面那个愚蠢的玩意儿吧

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int last = preorder.size() - 1;
        return build(preorder, inorder, 0, 0, last);
    }

    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int root, int start, int end) {
        if(start > end) return NULL;
        int val = preorder[root], i = start;
        while(i < end && val != inorder[i]) i++;
        TreeNode* r = new TreeNode(val);
        r->left  = build(preorder, inorder, root + 1, start, i - 1);
        r->right = build(preorder, inorder, root + i + 1 - start, i + 1, end);
        return r;
    }
};

98. Validate Binary Search Tree

解法一：中序遍历

判断BST，容易简单认为是只要左子树比根节点小，右子树比根节点大，以此递归就行

但是，上述策略忽略了一点：左子树<右子树

因此必须保证这一点，考虑到BST的特性：中序遍历，得出以下解法

class Solution {
    List<Integer> inorder=new ArrayList<Integer>();
    public boolean isValidBST(TreeNode root) {
        inorder(root);
        for(int i=1;i<inorder.size();i++){ //检查中序遍历结果是否顺序即可
            if(inorder.get(i)<=inorder.get(i-1))return false;
        }
        return true;
    }

    public void inorder(TreeNode root){
        if(root!=null){
            inorder(root.left);
            inorder.add(root.val);
            inorder(root.right);
        }
    }
}

解法二：迭代法

边迭代边检查，还可以写成递归法，不过同理就不写了

class Solution {
    Stack<TreeNode> stack=new Stack<TreeNode>();
    public boolean isValidBST(TreeNode root) {
        if(root==null)return true;
        TreeNode curr=root;
        Integer val=null; //注意这里要用Integer而不是int，因为可以用null,不然无论设成什么都能被卡掉
        while(curr!=null || !stack.isEmpty()){
            while(curr!=null){
                stack.push(curr);
                curr=curr.left;
            }
            curr=stack.pop();
            if(val!=null && curr.val<=val){return false;} //错误判定
            val=curr.val;
            curr=curr.right;
        }
        return true;
    }
}

102. Binary Tree Level Order Traversal

解法一：队列

标准层次遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == NULL) return {};
        std::queue<TreeNode*> q;
        q.push(root);
        vector<int> tmp;
        vector<vector<int>> res;
        while(!q.empty()){
            int len = q.size();
            for(int i = 0; i < len; i++){
                TreeNode* curr = q.front(); q.pop();
                tmp.push_back(curr->val);
                if(curr->left)  q.push(curr->left);
                if(curr->right) q.push(curr->right);
            }
            res.push_back(tmp);
            tmp.clear();
        }
        return res;
    }
};

103. Binary Tree Zigzag Level Order Traversal

解法一：队列

同上题，但是要求每一层反转顺序，因此

如果从左往右，那么同上题
如果从右往左，从队列尾端取节点，并且对应子节点逆序送入队首

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(root == NULL) return {};
        deque<TreeNode*> q; q.push_back(root);
        vector<int> tmp; vector<vector<int>> res;
        bool left = true;
        while(!q.empty()){
            int len = q.size();
            for(int i = 0; i < len; i++){
                TreeNode* curr;
                if(left) {
                    curr = q.front(); q.pop_front();
                    if(curr->left)  q.push_back(curr->left);
                    if(curr->right) q.push_back(curr->right);
                }
                else {
                    curr = q.back(); q.pop_back();
                    if(curr->right) q.push_front(curr->right);
                    if(curr->left)  q.push_front(curr->left);
                }
                tmp.push_back(curr->val);
            }
            res.push_back(tmp);
            tmp.clear();
            left = !left;
        }
        return res;
    }
};

113. Path Sum II

解法一：递归法

递归就完了，和Ⅰ完全一样

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<int> tmp;
        findSum(root, sum, tmp);
        return res;
    }

    void findSum(TreeNode* root, int sum, vector<int> tmp){
        if(root == NULL) return;
        sum -= root->val;
        tmp.push_back(root->val);
        if(sum == 0 && !root->left && !root->right){
            res.push_back(tmp);
            return;
        }
        findSum(root->left, sum, tmp);
        findSum(root->right, sum, tmp);
        return;
    }
};

114. Flatten Binary Tree to Linked List

解法一：递归法

基本原则就是，把左子树删除，并接到右子树，而原来的右子树再接到新的右子树的最右处，递归展开左右子树

class Solution {
public:
    void flatten(TreeNode* root) {
        if(root == NULL || (!root->left && !root->right)) return;
        TreeNode* left = root->left, * right = root->right, * curr = root;
        flatten(left);
        flatten(right);
        curr->left  = NULL;
        curr->right = left;
        while(curr->right) curr = curr->right;
        curr->right = right;
        return;
    }
};

129. Sum Root to Leaf Numbers

解法一：递归法

同pathSum系列，先把所有pathSum算出来存到一个vector，最后再累加

class Solution {
public:
    vector<int> vals;
    int sumNumbers(TreeNode* root) {
        getSum(root, 0);
        int sum = 0;
        for(int i : vals)
            sum += i;
        return sum;
    }

    void getSum(TreeNode* root, int sum){
        if(root == NULL) return;
        sum = sum * 10 + root->val;
        if(root->left == NULL && root->right == NULL)
            vals.push_back(sum);
        getSum(root->left , sum);
        getSum(root->right, sum);
    }
};

116. Populating Next Right Pointers in Each Node

解法一：层序遍历

第一想法应该就是这个了吧

class Solution {
public:
    Node* connect(Node* root) {
        if(root == NULL) return NULL;
        queue<Node*> q;
        q.push(root);
        while(q.size()){
            int len = q.size();;
            for(int i = 0; i < len; i++) {
                Node* curr = q.front(); q.pop();
                if(i != len - 1) curr->next = q.front();
                if(curr->left  != NULL)  q.push(curr->left);
                if(curr->right != NULL)  q.push(curr->right);
            }
        }
        return root;
    }
};

572. Subtree of Another Tree

虽然标的是简单，但是这题多解作为medium不过分

解法一：dfs

最直接的思路，用判同的方法来分别测试s的每个子节点是否和t是相同的，但是显然会有很多重复的搜索

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(s == nullptr) return false;
        return isSame(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
    }
    bool isSame(TreeNode* s, TreeNode* t) {
        if(s == nullptr && t == nullptr) return true;
        if(s == nullptr || t == nullptr || s->val != t->val) return false;
        return isSame(s->left, t->left) && isSame(s->right, t->right);
    }
};

230. Kth Smallest Element in a BST

解法一：先序遍历

直接先序遍历出来，取第k个

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        if(root == NULL) return 0;
        vector<int> inorder = dfs(root, vector<int>());
        return inorder[k - 1];
    }

    vector<int> dfs(TreeNode* root, vector<int> v) {
        if(root == NULL) return v;
        v = dfs(root->left, v);
        v.push_back(root->val);
        v = dfs(root->right, v);
        return v;
    }
};

**优化版：**遍历到第k个时就可以直接return了

class Solution {
public:
    int cnt;
    vector<int> inorder; 
    int kthSmallest(TreeNode* root, int k) {
        if(root == NULL) return 0;
        cnt = k;
        dfs(root);
        int len = inorder.size();
        return inorder[len - 1];
    }

    void dfs(TreeNode* root) {
        if(root == NULL) return;
        dfs(root->left);
        if(inorder.size() < cnt) inorder.push_back(root->val);
        dfs(root->right);
    }
};

迭代法：

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> stack;
        TreeNode* curr = root;
        while (curr != NULL || !stack.empty()) {
            while(curr != NULL) {
                stack.push(curr);
                curr = curr->left;
            }
            curr = stack.top(); stack.pop();
            if(--k == 0) return curr->val;
            curr = curr->right;
        }
        return -1;
    }
};

109. Convert Sorted List to Binary Search Tree

解法一：直接法

链表查中点和重建BST的组合题

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(head == NULL) return NULL;
        if(head->next == NULL) return new TreeNode(head->val);
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* slow = dummy, * fast = dummy->next;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        TreeNode* root = new TreeNode(slow->next->val);
        TreeNode* right = sortedListToBST(slow->next->next);
        slow->next = NULL;
        TreeNode* left = sortedListToBST(dummy->next);
        root->left = left;
        root->right = right;
        return root;
    }
};

解法二：先转数组

难度还降一级，但是更快一点，因为数组找中点可以直接算出来，注意取中点要向上取整

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(head == NULL) return NULL;
        vector<int> list;
        ListNode* curr = head;
        for(curr; curr != NULL; curr = curr->next)
            list.push_back(curr->val);
        return arrayListToBST(list, 0, list.size() - 1);
    }

    TreeNode* arrayListToBST(const vector<int>& nums, int i, int j) {
        if(i > j) return NULL;
        if(i == j) return new TreeNode(nums[i]);
        int mid = ceil((i + j) / 2.0);
        TreeNode* root = new TreeNode(nums[mid]), * left, * right;
        left = arrayListToBST(nums, i, mid - 1);
        right = arrayListToBST(nums, mid + 1, j);
        root->left = left;
        root->right = right;
        return root;
    }
};

236. 二叉树的最近公共祖先

解法一：递归法

首先判断两个子节点之间的父子关系，能省掉很多时间1200ms -> 20ms的区别
然后递归判断左右子树是否是父节点，如果是则往下走，否则判断根节点是否满足
- 如果满足，则返回根节点
- 否则返回NULL

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || !p || !q) return NULL;
        if(isSubNode(p, q)) return p;
        if(isSubNode(q, p)) return q;
        return checkDeeper(root, p, q);
    }

    TreeNode* checkDeeper(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return NULL;
        TreeNode* left = checkDeeper(root->left, p, q);
        TreeNode* right = checkDeeper(root->right, p, q);
        
        if(isSubNode(root, p) && isSubNode(root, q)) {
            if(!left && !right) return root;
            return left == NULL ? right : left;
        }
        return NULL;
    }

    bool isSubNode(TreeNode* s, TreeNode* t) {
        if(!s) return false;
        if(s == t) return true;
        return isSubNode(s->left, t) || isSubNode(s->right, t);
    }
};

**优化版，**减少了一些重复搜索

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return NULL;
        if(root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left && right) return root;
        return left ? left : right;
    }
};

501. Find Mode in Binary Search Tree

解法一：递归法

本来是很简单的统计问题，但是要求原地解决

利用BST的有序特性
问题转换为有序数组求众数的问题

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        if(!root) return {};
        vector<int> inorder;
        dfs(root, inorder);
        vector<int> res = { inorder[0] };
        int max_cnt = 1, cnt = 1, base = inorder[0];
        for(int i = 1; i < inorder.size(); ++i) {
            if(inorder[i] == base)
                ++cnt;
            else {
                cnt = 1;
                base = inorder[i];
            }
            if(cnt == max_cnt)
                res.push_back(inorder[i]);
            else if (cnt > max_cnt) {
                max_cnt = cnt;
                res = { base };
            }
        }
        return res;
    }

    void dfs(TreeNode* root, vector<int>& inorder) {
        if(!root) return;
        dfs(root->left, inorder);
        inorder.push_back(root->val);
        dfs(root->right, inorder);
    }
};

解法二：迭代法

class Solution {
public:
    int base, count, maxCount;
    vector<int> answer;

    void update(int x) {
        if (x == base) {
            ++count;
        } else {
            count = 1;
            base = x;
        }
        if (count == maxCount) {
            answer.push_back(base);
        }
        if (count > maxCount) {
            maxCount = count;
            answer = vector<int> {base};
        }
    }

    vector<int> findMode(TreeNode* root) {
        TreeNode *cur = root, *pre = nullptr;
        while (cur) {
            if (!cur->left) {
                update(cur->val);
                cur = cur->right;
                continue;
            }
            pre = cur->left;
            while (pre->right && pre->right != cur) {
                pre = pre->right;
            }
            if (!pre->right) {
                pre->right = cur;
                cur = cur->left;
            } else {
                pre->right = nullptr;
                update(cur->val);
                cur = cur->right;
            }
        }
        return answer;
    }
};

Tree-Medium

解法一：递归法

解法二：迭代法

解法三： 莫比斯遍历

解法一：递归法

解法二：记忆化递归

解法一：递归法

解法二：记忆化递归

解法一：递归法

新写法，忘了上面那个愚蠢的玩意儿吧

解法一：中序遍历

解法二：迭代法

解法一：队列

解法一：队列

解法一：递归法

解法一：递归法

解法一：递归法

解法一：层序遍历

解法一：dfs

解法一：先序遍历

解法一：直接法

解法二：先转数组

解法一：递归法

解法一：递归法

解法二：迭代法

解法三：莫比斯遍历