day5

• 求一棵树的最大深度

  • 深度优先遍历
    
    对于左子树和右子树进行递归,如果哪个值比较大,我们就可以进行保存,值得注意的是,我们应该将这一轮的值进行保存

    class Solution {
      public int maxDepth(TreeNode root) {
          if(root==null){
              return 0;
          }
          else{
          int leftHeight=maxDepth(root.left);
          int rightHeight=maxDepth(root.right);
          return Math.max(leftHeight,rightHeight)+1;
          }
      }
    } 

  • 正统dfs想法和我第一遍想的一样,写不出来hhhhh
    其中极端情况去想这个递归的是,我们只有一颗全部是左子树的树,这时候我们就要不停的向左走,如果走到头我们就要进行回退进行判断
    
    另外,如果只有一个节点的,我们就想要进行判断是否是叶子节点,这时候我们期望的是返回节点,进行判断父节点是否有兄弟

    class Solution {
      int height = 0;
      int ans = 0;
      public int maxDepth(TreeNode root) {
          traverse(root);
          return ans;
      }
      public void traverse(TreeNode root){
          if(root==null){
              return;
          }
          height ++;
          ans = Math.max(ans,height);
          traverse(root.left);
          traverse(root.right);
          height--;
      }
    }

  • 层序遍历

    class Solution {
      public int maxDepth(TreeNode root) {
          if(root==null)
              return 0;
          List<TreeNode> queue = new LinkedList<>(),temp;//注意声明
          int ans = 0;
          queue.add(root);
          while(!queue.isEmpty()){
              temp = new LinkedList<>();
              for(TreeNode treeNode : queue){
                  if(treeNode.left!=null)
                      temp.add(treeNode.left);
                  if(treeNode.right!=null)
                      temp.add(treeNode.right); 
              }
              queue = temp;
              ans++;
          }
          return ans;
      }
    }

• 对称二叉树

  • 使用栈完成,思想和递归类似,但是脑子想不清楚,fufufufuffuf

    import java.util.LinkedList;
    
    class Solution {
      public boolean isSymmetric(TreeNode root) {
          if (root == null) {
              return true;
          }
    
          LinkedList<TreeNode> nstack = new LinkedList<>();
          nstack.push(root.left);
          nstack.push(root.right);
    
          while (!nstack.isEmpty()) {
              TreeNode right = nstack.pop();
              TreeNode left = nstack.pop();
    
              if (right == null && left == null) {
                  continue;
              }
    
              if (right == null || left == null || right.val != left.val) {
                  return false;
              }
    
              // 对称位置的节点入栈，注意入栈顺序
              nstack.push(left.left);
              nstack.push(right.right);
              nstack.push(left.right);
              nstack.push(right.left);
          }
    
          return true;
      }
    }

  • 每次看了递归只能喵喵喵的叫,1.添加跳出循环的条件

    class Solution {
      public boolean isSymmetric(TreeNode root) {
          return isSymmetric(root, root);
      }
    
      public boolean isSymmetric(TreeNode node1, TreeNode node2) {
          if (node1 == null && node2 == null) {
              return true;
          }
          if (node1 == null || node2 == null || node1.val != node2.val) {
              return false;
          }
          return isSymmetric(node1.left, node2.right) && isSymmetric(node1.right, node2.left);
      }
    }

• 总结一下:
  使用 ArrayList 实现队列和栈队列操作：
  加入元素： 使用 add 方法将元素添加到 ArrayList 的末尾。

  Copy code
  ArrayList<TreeNode> queue = new ArrayList<>();
  queue.add(element);

  删除元素： 使用 remove(0) 方法移除第一个元素。

Copy code
TreeNode removedElement = queue.remove(0);
栈操作：

加入元素： 使用 add 方法将元素添加到 ArrayList 的末尾。

Copy code
ArrayList<TreeNode> stack = new ArrayList<>();
stack.add(element);

删除元素： 使用 remove(size - 1) 方法移除最后一个元素。

Copy code
TreeNode removedElement = stack.remove(stack.size() - 1);
使用 LinkedList 实现队列和栈

队列操作：
加入元素： 使用 offer 方法将元素添加到 LinkedList 的末尾。

Copy code
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(element);

删除元素： 使用 poll 方法移除并返回第一个元素。

Copy code
TreeNode removedElement = queue.poll();

栈操作：
加入元素： 使用 addFirst 或 push 方法将元素添加到 LinkedList 的开头。

Copy code
LinkedList<TreeNode> stack = new LinkedList<>();
stack.addFirst(element);
// 或
stack.push(element);

删除元素： 使用 removeFirst 或 pop 方法移除并返回第一个元素。

Copy code
TreeNode removedElement = stack.removeFirst();
// 或
TreeNode poppedElement = stack.pop();