leetCode 101/199-Symmetric Tree/Binary Tree Right Side View

青旅半醒 2022-08-07 11:39 23阅读 0赞

一：leetcode 101 [Symmetric Tree][]

题目：

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

1
       / \
      2   2
     / \ / \
    3  4 4  3

But the following is not:

1
       / \
      2   2
       \   \
       3    3

此题就是判断一棵二叉树是否为对称二叉树，刚开始以为中序遍历输出，然后看是否是为回文字串，但是这种思路是错了，如\[1,2,3,\#,3,\#,2\].

代码如下：

通过判断左孩子的左子树与右孩子的右子树 及 左孩子的右子树与右孩子的左子树

class Solution {
    public:
        bool isJudging(TreeNode *nodeLeft, TreeNode *nodeRight){
            if(nodeLeft != NULL && nodeRight != NULL && nodeLeft->val == nodeRight->val){
                return isJudging(nodeLeft->left, nodeRight->right) & isJudging(nodeLeft->right, nodeRight->left);
            }
            else if(nodeLeft == NULL && nodeRight == NULL)
                return true;
            else return false;
            
        }
        bool isSymmetric(TreeNode *root) {
            if(root == NULL) return true;
            return isJudging(root->left, root->right);
        }
    };

以上是判断是否为对称二叉树，下面是将一棵二叉树反转，采用递归的方法，要注意递归的结束条件，然后向上不断进行，就会将左右子树再变成对称二叉树了。。。居然没写出来。。。。fuck

struct TreeNode{
    	TreeNode *l, *r;
    	int value;
    	TreeNode(int v):value(v){l=NULL; r = NULL;}
    };
    
    
    
    class Solution{
    public:
    	void reverseTree(TreeNode *p){
    		if(p == NULL) return ;
    		if(p->l == NULL && p->r != NULL){p->l = p->r; p->r = NULL;}
    		if(p->l != NULL && p->r == NULL){p->r = p->l; p->l = NULL;}
    		reverseTree(p->l);
    		reverseTree(p->r);
    		swap(p->l, p->r);
    	}
    };

二：leetcode199 [Binary Tree Right Side View][]

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:  
Given the following binary tree,

1            <---
     /   \
    2     3         <---
     \     \
      5     4       <---

You should return `[1, 3, 4]`.

分析：此题思路是DFS，但是先DFS右子树，便求出最右的最大深度，每当深度超过最大深度，则将该结点加入到result中，并更新最大深度

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        void dfs(int dep, int &maxDep, TreeNode *p){
            if(p == NULL) return;
            if(dep > maxDep) {   // 当深度大于最大深度时，将其加入到result中
                maxDep = dep;
                result.push_back(p->val);  
            }
            dfs(dep+1, maxDep, p->right);    // 先遍历右子树，得到右子树最深深度，再遍历其左节点
            dfs(dep+1, maxDep, p->left);
        }
        vector<int> rightSideView(TreeNode *root) {
            int maxDep = -1;
            dfs(0, maxDep, root);
            return result;
            
        }
    private:
        vector<int> result;
    };

[Symmetric Tree]: https://leetcode.com/problems/symmetric-tree/
[Binary Tree Right Side View]: https://leetcode.com/problems/binary-tree-right-side-view/