LeetCode--Symmetric Tree

た入场券 2022-08-18 00:56 34阅读 0赞

**Problem:**

> 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
> 
> Note: Bonus points if you could solve it both recursively and  
> iteratively. confused what “\{1,\#,2,3\}” means? > read more on how  
> binary tree is serialized on OJ. Subscribe to see which companies  
> asked this question

**Analysis:**  
方法1：再次创建一个新的函数，该函数有两个参数，一个是左节点，另一个是右节点，利用这两个记录的节点，分别判断**左节点的左孩子？=右节点的右孩子**；**左节点的右孩子？=右节点的左孩子**，将判断的结果返回；  
这里其实的对两棵子树同时进行递归判断。  
方法2：利用堆栈将节点按照特点的顺序（**左节点压左孩子，右节点就得压右孩子；左节点压右孩子，右节点就得压左孩子**）压入堆栈，把相应的节点作比较，不相同则返回false，相同的话就continue或者压入堆栈。  
**Anwser1:**  
递归：

public class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        //recursively
            if(root==null) return true;
            else return isSymmetric(root.left,root.right);
        }
        public boolean isSymmetric(TreeNode leftNode,TreeNode rightNode){
            if(leftNode==null && rightNode==null) return true;
            else if (leftNode==null || rightNode==null) return false;
            else {
                if (leftNode.val==rightNode.val) {
                    boolean leftSym = isSymmetric(leftNode.left,rightNode.right);
                    boolean rightSym = isSymmetric(leftNode.right,rightNode.left);
                    return leftSym && rightSym;
                }
                else return false;
            }
        } 
    }

**Anwser2:**  
迭代

public class Solution {
        public boolean isSymmetric(TreeNode root) {
            if(root==null) return true;
            Stack<TreeNode> leftStack = new Stack<TreeNode>();
            Stack<TreeNode> rightStack = new Stack<TreeNode>();
            leftStack.push(root.left);
            rightStack.push(root.right);
            while(leftStack.size()>0 && rightStack.size()>0){
                TreeNode leftNode = leftStack.pop();
                TreeNode rightNode = rightStack.pop();
                if(leftNode==null && rightNode==null) continue;//不能返回true,因为还有其他没有比较的节点。
                else if(leftNode==null || rightNode==null) return false;
                else if(leftNode.val==rightNode.val){
                    //压入堆栈的顺序要注意
                    leftStack.push(leftNode.left);
                    leftStack.push(leftNode.right);
                    rightStack.push(rightNode.right);
                    rightStack.push(rightNode.left);
                }
                else return false;//考虑的是leftNode.val!=rightNode.val的情况，不能丢
            }
            return true;//考虑的是完全对称的树，最后应该返回true,不能丢
        } 
    }