代码随想录Day12 二叉树 LeetCode T102二叉树的层序遍历 T226 翻转二叉树 T101 对称二叉树

本文思路和详细讲解来自于:代码随想录 (programmercarl.com)

LeetCode T102 二叉树的层序遍历

题目链接:102. 二叉树的层序遍历 - 力扣（LeetCode）

题目思路:

本题使用队列辅助完成,讲解主要函数CheckOrder:首先判断root是否为空,是就直接返回,然后创建队列,向里加入root元素,计算队列的长度,也就是每一层的元素个数,while循环,size--为结束条件,每层的数组用tmp记录一下,循环内用临时node记录一下root的val,并将root移出队列,判断左右子树是否为空,不是就入队,出循环之后将数组加入二维数组.

题目代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List> result = new ArrayList<>();
    public List> levelOrder(TreeNode root) {
        CheckOrder(root);
        return result;
 
    }
     public void  CheckOrder(TreeNode node)
     {
        if(node == null)
        {
            return;
        }
        Queue que = new LinkedList<>();
        que.offer(node);
        while(!que.isEmpty())
        {
            List tmp = new ArrayList<>();
            int size = que.size();
            while(size>0)
            {
                TreeNode tmpNode = que.poll();
                tmp.add(tmpNode.val);
                if(tmpNode.left != null)
                {
                    que.offer(tmpNode.left);
                }
                if(tmpNode.right != null)
                {
                    que.offer(tmpNode.right);
                }
                size--;
            }
            result.add(tmp);
        }
 
         
     }
}

LeetCode T226 翻转二叉树

题目链接:226. 翻转二叉树 - 力扣（LeetCode）

题目思路:

我们来看一下递归三部曲：

1.确定递归函数的参数和返回值

参数就是要传入节点的指针，不需要其他参数了，通常此时定下来主要参数，如果在写递归的逻辑中发现还需要其他参数的时候，随时补充。

TreeNode invertTree(TreeNode root)

2.确定终止条件

当前节点为空的时候，就返回

 if(root == null)
    {
        return root;
    }

3.确定单层递归的逻辑

因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。

         Swap(root);
        invertTree(root.left);
        invertTree(root.right);

题目代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null)
        {
            return root;
        }
        Swap(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;
 
    }
    public void Swap(TreeNode root)
    {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

LeetCode T101 对称二叉树

题目链接:

题目思路:

我们用递归实现,首先我们要清楚比较的是左右节点而不是左右孩子,其实就是左右外侧和内侧分别作比较,无非就是一下几种情况,

在分别处理内外侧,最后进行与操作即可

为什么是后序遍历?

本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。

正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。

题目代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return cmp(root.left,root.right);
        
       
 
    }
    boolean cmp(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(right.val !=left.val)
        {
            return false;
        }
        boolean outSide = cmp(left.left,right.right);
 
        boolean inSide = cmp(left.right,right.left);
        return outSide && inSide;
    }
}