美文网首页
左右二叉树

左右二叉树

作者: 程序员乔戈里 | 来源:发表于2020-12-19 19:23 被阅读0次

    题目

    思路

    找到递归点:左树与右树对称与否,与其跟两树的子树的对称情况有关系。

    递归结束条件:

    • 都为空指针则返回 true
    • 只有一个为空则返回 false
    • 两个指针当前节点值不相等 返回false

    递归过程:

    • 判断 A 的右子树与 B 的左子树是否对称
    • 判断 A 的左子树与 B 的右子树是否对称

    图解思路

    https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/solution/mian-shi-ti-28-dui-cheng-de-er-cha-shu-di-gui-qing/










    代码实现

    C++

    class Solution {
    public:
        bool compare(TreeNode* left, TreeNode* right) {
            // 首先排除空节点的情况
            if (left == NULL && right != NULL) return false;
            else if (left != NULL && right == NULL) return false;
            else if (left == NULL && right == NULL) return true;
            // 排除了空节点,再排除数值不相同的情况
            else if (left->val != right->val) return false;
    
            // 此时就是:左右节点都不为空,且数值相同的情况
            // 此时才做递归,做下一层的判断
            bool outside = compare(left->left, right->right);   // 左子树:左、 右子树:右
            bool inside = compare(left->right, right->left);    // 左子树:右、 右子树:左
            bool isSame = outside && inside;                    // 左子树:中、 右子树:中 (逻辑处理)
            return isSame;
    
        }
        bool isSymmetric(TreeNode* root) {
            if (root == NULL) return true;
            return compare(root->left, root->right);
        }
    };
    

    Java

    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        //从两个子节点开始判断
        return isSymmetricHelper(root.left, root.right);
    }
    
    public boolean isSymmetricHelper(TreeNode left, TreeNode right) {
        //如果左右子节点都为空,说明当前节点是叶子节点,返回true
        if (left == null && right == null)
            return true;
        //如果当前节点只有一个子节点或者有两个子节点,但两个子节点的值不相同,直接返回false
        if (left == null || right == null || left.val != right.val)
            return false;
        //然后左子节点的左子节点和右子节点的右子节点比较,左子节点的右子节点和右子节点的左子节点比较
        return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
    }
    

    Python

    class Solution(object):
        def isSymmetric(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            if not root:
                return True
            def dfs(left,right):
                # 递归的终止条件是两个节点都为空
                # 或者两个节点中有一个为空
                # 或者两个节点的值不相等
                if not (left or right):
                    return True
                if not (left and right):
                    return False
                if left.val!=right.val:
                    return False
                return dfs(left.left,right.right) and dfs(left.right,right.left)
            # 用递归函数,比较左节点,右节点
            return dfs(root.left,root.right)
    

    Js

    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {boolean}
     */
    var isSame = function(root1,root2){
        let r1,r2;
        if(root1==null || root2==null)
        {
            if(root1==null && root2==null)
                return true;
            else
                return false;
        }
        if(root1.val!==root2.val)
            return false; 
        r1 =  isSame(root1.left,root2.right);
        r2 =  isSame(root1.right,root2.left);
        return r1 & r2;
    }
    var isSymmetric = function(root) {
        if(root == null)
            return true;
    //判断根左子树是否和根右子树对称   递归的那l.left和r.right 以及 l.right 和r.left比较
        return isSame(root.left,root.right);
    };
    
    

    迭代法

    这道题目我们也可以使用迭代法,但要注意,这里的迭代法可不是前中后序的迭代写法,因为本题的本质是判断两个树是否是相互翻转的,其实已经不是所谓二叉树遍历的前中后序的关系了。

    这里我们可以使用队列来比较两个树(根节点的左右子树)是否相互翻转,(注意这不是层序遍历)

    使用队列
    通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等,如动画所示:

    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            if (root == NULL) return true;
            queue<TreeNode*> que;
            que.push(root->left);   // 将左子树头结点加入队列
            que.push(root->right);  // 将右子树头结点加入队列
            while (!que.empty()) {  // 接下来就要判断这这两个树是否相互翻转
                TreeNode* leftNode = que.front(); que.pop();    
                TreeNode* rightNode = que.front(); que.pop();
                if (!leftNode && !rightNode) {  // 左节点为空、右节点为空,此时说明是对称的
                    continue;
                }
    
                // 左右一个节点不为空,或者都不为空但数值不相同,返回false
                if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) { 
                    return false;
                }
                que.push(leftNode->left);   // 加入左节点左孩子
                que.push(rightNode->right); // 加入右节点右孩子
                que.push(leftNode->right);  // 加入左节点右孩子
                que.push(rightNode->left);  // 加入右节点左孩子
            }
            return true;
        }
    };
    
    

    使用栈

    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            if (root == NULL) return true;
            stack<TreeNode*> st; // 这里改成了栈
            st.push(root->left);
            st.push(root->right);
            while (!st.empty()) {
                TreeNode* leftNode = st.top(); st.pop();
                TreeNode* rightNode = st.top(); st.pop();
                if (!leftNode && !rightNode) {
                    continue;
                }
                if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                    return false;
                }
                st.push(leftNode->left);
                st.push(rightNode->right);
                st.push(leftNode->right);
                st.push(rightNode->left);
            }
            return true;
        }
    };
    
    

    相关文章

      网友评论

          本文标题:左右二叉树

          本文链接:https://www.haomeiwen.com/subject/otvcnktx.html