Map of Augustus's Soul

Algo Revised: Tree

Posted on Edited on In Valine:
Symbols count in article: 14k Reading time ≈ 35 mins.

101. Symmetric Tree

从树的递归性质入手 这里增加的难度在于左右交替判断 注意指针为空的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isSym(TreeNode* rt1,TreeNode*rt2)
    {
        if(!rt1&&!rt2)
            return true;
        else if(rt1 && rt2)
        {
            if(rt1->val!=rt2->val)
                return false;
            return isSym(rt1->left,rt2->right) && isSym(rt1->right,rt2->left);
        }
        else
            return false;
    }
    bool isSymmetric(TreeNode* root) {
        return isSym(root->left,root->right);
    }
};

98. Validate Binary Search Tree

搜索树的定义！！复习非递归实现前序遍历

递归：结合范围 注意数字取值的范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool check(long long lower,long long upper, TreeNode* root)
    {
        if(!root)
            return true;
        if(root->val <= lower || root->val >= upper)
            return false;
        return check(lower,root->val,root->left) && 
        check(root->val,upper,root->right);
    }
    bool isValidBST(TreeNode* root) {
        return check(LONG_MIN,LONG_MAX,root);
    }
};

非递归的中序遍历

甚至都不需要存队列 只需要保存队列的最后一个值进行比较就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stk;
        long long inorder = LONG_MIN;
        while(!stk.empty() || root)
        {
            while(root)
            {
                stk.push(root);
                root=root->left;
            }
            root = stk.top();
            stk.pop();
            if(inorder>=root->val)
                return false;
            inorder = root->val;
            root=root->right;
        }
        return true;
    }
};

104. Maximum Depth of Binary Tree

复习一下切分递归的方式 广度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int twoSide(TreeNode* ltree,TreeNode* rtree)
    {
        int lDepth=0,rDepth=0;
        if(ltree)
            lDepth = twoSide(ltree->left,ltree->right);
        if(rtree)
            rDepth = twoSide(rtree->left,rtree->right);
        return 1+max(lDepth,rDepth);
    }
    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        return twoSide(root->left,root->right);
    }
};

其他方法：深度优先递归 不使用全局变量

1
2
3
4
5
6
7
8
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        return 1+max(maxDepth(root->left),maxDepth(root->right));
    }
};

105. Construct Binary Tree from Preorder and Inorder Traversal

美区评论区大神 StefanPochmann

Consider the example again. Instead of finding the 1 in inorder, splitting the arrays into parts and recursing on them, just recurse on the full remaining arrays and stop when you come across the 1 in inorder. That’s what my above solution does. Each recursive call gets told where to stop, and it tells its subcalls where to stop. It gives its own root value as stopper to its left subcall and its parent`s stopper as stopper to its right subcall.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    int index = 0;
    int preIndex = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return partition(Integer.MAX_VALUE+1,preorder,inorder);
    }
    TreeNode partition(int stop,int[] preorder,int[] inorder){
        if(index<inorder.length && inorder[index]!=stop){
            TreeNode root = new TreeNode(preorder[preIndex++]);
            root.left = partition(root.val,preorder,inorder);
            //左子树遍历完成后index指向root
            index++;
            //开始遍历右侧 其中右侧应当停下的位置与上一层指定的stop位置相同
            //右侧遍历和左侧一样 先建立左子树 递归思路
            root.right = partition(stop,preorder,inorder);
            return root;
        }
        return null;
    }
}

102. Binary Tree Level Order Traversal

一开始想到广度优先的填色法来交替区分不同层次，答案给出了更小空间的做法：统计当前队列中点的个数 只取出这些作为一列 

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
27
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> que;
        if(root)
            que.push(root);
        while(!que.empty())
        {
            TreeNode* tmp;
            vector<int> line;
            int lineCount = que.size();
            for(int i=0;i<lineCount;++i)
            {
                tmp = que.front();
                que.pop();
                line.push_back(tmp->val);
                if(tmp->left)
                    que.push(tmp->left);
                if(tmp->right)
                    que.push(tmp->right);
            }
            res.push_back(line);
        }
        return res;
    }
};

用分而治之的思路来解决这个看似复杂的问题：先搞好根节点 递归的构建子节点

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
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    TreeNode* partBuild(vector<int>& preorder,int rootpos,vector<int>&inorder,int left,int right)
    {
        //cout<<rootpos<<" "<<left<<" "<<right<<endl;
        if(rootpos>=preorder.size() || rootpos<0)//|| left>right
            return nullptr;
        TreeNode* res = new TreeNode(preorder[rootpos]);
        if(left==right)
        {
            return res;
        }
        res = new TreeNode(preorder[rootpos]);
        //cout<<res->val<<endl;
        int inpos=-1;
        for(int i=left;i<=right;++i)
        {
            if(inorder[i]==preorder[rootpos])
            {
                inpos = i;
                break;
            }
        }
        int leftlen = inpos-left;
        if(leftlen!=0)//记得给两个子树加条件 未必有子树
            res->left = partBuild(preorder,rootpos+1,inorder,left,inpos-1);
        if(inpos+1<=right)//救命 debug了半天 或者注释掉两个if 在开头加上 
            res->right = partBuild(preorder,rootpos+leftlen+1,inorder,inpos+1,right);
        return res;
        
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        
        return partBuild(preorder,0,inorder,0,inorder.size()-1);
    }
};

复习preorder

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
27
28
29
class Solution {
public:
    void flatten(TreeNode* root) {
        if(!root)
            return;
        TreeNode*ptr=root;
        stack<TreeNode*> stk;
        vector<TreeNode*> vec;
        while(!stk.empty() || ptr)
        {
            while(ptr)
            {
                vec.push_back(ptr);
                stk.push(ptr);
                ptr=ptr->left;
            }
            ptr=stk.top();
            stk.pop();
            ptr=ptr->right;
        }
        ptr=root;
        for(int i=1;i<vec.size();++i)
        {
            ptr->right=vec[i];
            ptr->left=nullptr;
            ptr=ptr->right;
        }
    }
};

一边遍历一边修改树的难点在于同时保存左右节点的信息

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
class Solution {
public:
    void flatten(TreeNode* root) {
        if(!root)
            return ;
        TreeNode* prev=nullptr,*curr=nullptr;
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty())
        {
            curr= stk.top();
            stk.pop();
            if(prev)
            {
                prev->left=nullptr;
                prev->right=curr;
            }
            prev=curr;
            if(curr->right)
                stk.push(curr->right);
            if(curr->left)
                stk.push(curr->left);
        }
    }
};

最理想的状态是 原地完成 关键是找前驱：在前序遍历中 左子树最右侧的节点是右子树的前驱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void flatten(TreeNode* root) {
        if(!root)  
            return;
        TreeNode* curr=root,*next=nullptr;
        while(curr)
        {
            if(curr->left)
            {
                next=curr->left;
                auto pred = next;
                while(pred->right)
                    pred=pred->right;
                pred->right=curr->right;
                curr->left=nullptr;
                curr->right=next;
            }
            curr=curr->right;
        }
    }
};

124. Binary Tree Maximum Path Sum

利用分治的思想分析的时候还应该考虑完整的情况 比如作为答案最大值有几种来源（根，根和子树之一，绕过根两棵子树，子树），以及作为子树路径最大值有几种可能（根本身，根和其中一棵子树）

多次提交失败中没有注意到的情况：

子树不能增益

根不能增益

最大值来源于：仅有根，根和两棵子树。根和单边子树

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
class Solution {
public:
    int ans=INT_MIN;
    int reverse(TreeNode* root)
    {
        if(!root)
            return 0;
        int leftres=0,rightres=0;
        if(root->left)
            leftres = reverse(root->left);
        if(root->right)
            rightres = reverse(root->right);
        ans = max(ans,root->val+leftres+rightres);//经过根节点
        ans = max(ans,root->val);//只有根节点
        ans = max(ans,max(leftres,rightres)+root->val);//经过单边
        //ans = max(ans)
        if(max(leftres,rightres)>0)
            return root->val+max(leftres,rightres);
        else
            return (root->val>0)?root->val:0;
    }
    int maxPathSum(TreeNode* root) {
        reverse(root);
        return ans;
    }
};

*236. Lowest Common Ancestor of a Binary Tree

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* ans;
//两侧检查 向上传递 只在有交汇的地方更新 剩下的不管 只管传递
    bool DFS(TreeNode* root, TreeNode* p, TreeNode* q){
        if(root==NULL)
            return false;
        bool lson = DFS(root->left,p,q);
        bool rson = DFS(root->right,p,q);
        if((lson && rson)||
        ((root->val == p->val || root->val == q->val)&&(lson || rson)) ){
            ans = root;
        }
        return lson || rson || root->val == p->val || root->val == q->val;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        DFS(root,p,q);
        return ans;
    }
};

哈希表记录父亲节点 再记录是否被遍历过 出现重复遍历的就返回

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
27
28
29
30
class Solution {
public:
    unordered_map<int,TreeNode*> father;
    unordered_map<int,bool> visited;
    void DFS(TreeNode* root){
        if(root->left!=NULL){
            father[root->left->val]=root;
            DFS(root->left);
        }
        if(root->right!=NULL){
            father[root->right->val]=root;
            DFS(root->right);
        }

    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        father[root->val]=NULL;
        DFS(root);
        while(p!=NULL){
            visited[p->val]=true;
            p = father[p->val];
        }
        while(q!=NULL){
            if(visited[q->val]==true)
                return q;
            q = father[q->val];
        }
        return NULL;
    }
};

297. Serialize and Deserialize Binary Tree

复习了层次遍历 关键在于存入空指针是无法构成联系的

复习了一些库的使用 包括利用stringstream以指定分割符分割字符串，int和string的互相转换

437. Path Sum III

原本的思路 用哈希表记录可能的结果——空间优化 记录需要的

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
27
28
29
class Solution {
public:
int rootSum(TreeNode* root, int targetSum) {
        if (!root) {
            return 0;
        }

        int ret = 0;
        if (root->val == targetSum) {
            ret++;
        } 

        ret += rootSum(root->left, targetSum - root->val);
        ret += rootSum(root->right, targetSum - root->val);
        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {
        if (!root) {
            return 0;
        }
        
        int ret = rootSum(root, targetSum);
        ret += pathSum(root->left, targetSum);
        ret += pathSum(root->right, targetSum);
        return ret;
    }

};

沿用类似的思路 是否加上自己本身 可以折叠成递归

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    //k=true 不包括本节点
    int pathSum(TreeNode* root, int targetSum,bool k=true) {
        return root? (
            pathSum(root->left,targetSum-root->val,false)
            +pathSum(root->right,targetSum-root->val,false) 
            +(k?(pathSum(root->left,targetSum,true)//有不包括的情况才能计入
                +pathSum(root->right,targetSum,true))
            :0)+(root->val==targetSum?1:0)
        ):0;
    }
};//空间打败的多

前缀和：记录根节点到当前节点的路径上 除去当前节点自身之外节点和

如果有一个节点n 其前缀和为curr 如果n到root路径上存在p点，前缀和为 curr-targetSum 那么p到n和为targetSum

有类似之前线性的一道题 记录本身 找与目标差值的key的哈希表用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    unordered_map<long long ,int> prefix;//curr对应的路径条数
    int dfs(TreeNode* root,long long curr,int targetSum)
    {
        if(!root)
            return 0;
        int ret=0;
        curr+=root->val;//accumulate
        if(prefix.count(curr-targetSum))
            ret = prefix[curr-targetSum];
        //search
        prefix[curr]++;
        ret+=dfs(root->left,curr,targetSum);
        ret+=dfs(root->right,curr,targetSum);
        prefix[curr]--;//从当前路径退出 避免干扰其他路径计数

        return ret;
    }
    int pathSum(TreeNode* root, int targetSum) {
        prefix[0]=1;//ini 假设一开始root->val==targetSum
        return dfs(root,0,targetSum);
    }
};

543. Diameter of Binary Tree

分析清除返回值的含义 争取一次bug free

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int ans;
    int sideLongest(TreeNode* root)
    {
        if(!root)
            return 0;
        int left = sideLongest(root->left);
        int right= sideLongest(root->right);
        ans = max(ans,right+left);
        return max(left,right)+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        ans=0;
        sideLongest(root);
        return ans;
    }
};

538. Convert BST to Greater Tree

可以原地！按照右中左反中序遍历 只需要累加并且把值赋予节点就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    //可以原地
    int sum=0;
    TreeNode* convertBST(TreeNode* root) {
        if(!root)
            return nullptr;
        convertBST(root->right);
        sum+=root->val;
        root->val=sum;
        convertBST(root->left);
        return root;
    }
};

617. Merge Two Binary Trees

深度优先 更简洁

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1)  
            return root2;
        if(!root2)
            return root1;
        TreeNode* root = new TreeNode(root1->val+root2->val);
        root->left = mergeTrees(root1->left,root2->left);
        root->right = mergeTrees(root1->right,root2->right);
        return root;
    }
};

广度优先 用牵引避免空指针 小心空指针的条件

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) {
            return t2;
        }
        if (t2 == nullptr) {
            return t1;
        }
        auto merged = new TreeNode(t1->val + t2->val);
        auto q = queue<TreeNode*>();
        auto queue1 = queue<TreeNode*>();
        auto queue2 = queue<TreeNode*>();
        q.push(merged);
        queue1.push(t1);
        queue2.push(t2);
        while (!queue1.empty() && !queue2.empty()) {
            auto node = q.front(), node1 = queue1.front(), node2 = queue2.front();
            q.pop();
            queue1.pop();
            queue2.pop();
            auto left1 = node1->left, left2 = node2->left, right1 = node1->right, right2 = node2->right;
            if (left1 != nullptr || left2 != nullptr) {
                if (left1 != nullptr && left2 != nullptr) {
                    auto left = new TreeNode(left1->val + left2->val);
                    node->left = left;
                    q.push(left);
                    queue1.push(left1);
                    queue2.push(left2);
                } else if (left1 != nullptr) {
                    node->left = left1;
                } else if (left2 != nullptr) {
                    node->left = left2;
                }
            }
            if (right1 != nullptr || right2 != nullptr) {
                if (right1 != nullptr && right2 != nullptr) {
                    auto right = new TreeNode(right1->val + right2->val);
                    node->right = right;
                    q.push(right);
                    queue1.push(right1);
                    queue2.push(right2);
                } else if (right1 != nullptr) {
                    node->right = right1;
                } else {
                    node->right = right2;
                }
            }
        }
        return merged;

    }
};

103. Binary Tree Zigzag Level Order Traversal

注意是整体的排序 需要用到栈

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
27
28
29
30
31
32
import java.util.*;
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Stack<TreeNode> stk = new Stack<TreeNode>();
        List<List<Integer>> ans = new LinkedList<>();
        stk.push(root);
        int cnt=0;
        while(!stk.empty()){
            List<Integer> list = new LinkedList<>();
            Stack<TreeNode> nextline = new Stack<TreeNode>();
            while(!stk.empty()){
                TreeNode node = stk.pop();
                if(node!=null){
                    list.add(node.val);
                    if(cnt%2==0){
                        nextline.push(node.left);
                        nextline.push(node.right);
                    }
                    else{
                        nextline.push(node.right);
                        nextline.push(node.left);
                    }
                }
            }
            if(!list.isEmpty())
                ans.add(list);
            stk.addAll(nextline);
            cnt++;
        }
        return ans;
    }
}

更简单的办法：层序遍历 在最终结果中取奇数位置的list倒序遍历

987. Vertical Order Traversal of a Binary Tree

自定义排序

注意自定排序的写法

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<int[]> nodes = new ArrayList<>();
        dfs(root,0,0,nodes);
        Collections.sort(nodes,new Comparator<int[]>(){
            @Override
            public int compare(int[] tuple1,int[] tuple2){
                if(tuple1[0]!=tuple2[0])
                    return tuple1[0]-tuple2[0];
                else if(tuple1[1]!=tuple2[1])
                    return tuple1[1]-tuple2[1];
                else    
                    return tuple1[2]-tuple2[2];
            }
        });
        List<List<Integer>> ans = new ArrayList<>();
        int size=0;
        int lastCol = Integer.MIN_VALUE;
        for(int[] tuple : nodes){
            int col = tuple[0];
            int row = tuple[1];
            int val = tuple[2];
            if(col!=lastCol){
                lastCol = col;
                ans.add(new ArrayList<Integer>());
                size++;
            }
            ans.get(size-1).add(val);
        }
        return ans;
    }
    void dfs(TreeNode root,int row,int col,List<int[]> nodes){
        if(root==null)
            return;
        int[] info = {col,row,root.val};  
        nodes.add(info);
        dfs(root.left,row+1,col-1,nodes);
        dfs(root.right,row+1,col+1,nodes);      
    }
}