Z 字型打印二叉树

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  18.         Stack<TreeNode> stack1 = new Stack<>();
  19.         Stack<TreeNode> stack2 = new Stack<>();
  20.         if (root == null){
  21.             return new ArrayList<>();
  22.         }
  23.         stack1.push(root);
  24.         List<List<Integer>> result = new ArrayList<>();
  25.         while(!stack1.empty()){
  26.             List<Integer> list1 = new ArrayList<>();
  27.             while(!stack1.empty()){
  28.                 TreeNode item = stack1.pop();
  29.                 list1.add(item.val);
  30.                 if (item.left != null){
  31.                     stack2.push(item.left);
  32.                 }
  33.                 if (item.right != null){
  34.                     stack2.push(item.right);
  35.                 }
  36.             }
  37.             result.add(list1);
  38.             List<Integer> list2 = new ArrayList<>();
  39.             while (!stack2.empty()){
  40.                 TreeNode item = stack2.pop();
  41.                 list2.add(item.val);
  42.                 if (item.right != null){
  43.                     stack1.push(item.right);
  44.                 }
  45.                 if (item.left != null){
  46.                     stack1.push(item.left);
  47.                 }
  48.             }
  49.             if (!list2.isEmpty()){
  50.                 result.add(list2);
  51.             }
  54.         }
  55.         return result;
  57.     }
  58. }

114 前序二叉树O（1）转链表

public TreeNode digui(TreeNode root){
    if (root == null){
        return null;
    }
        if (root.left == null && root.right == null){
            return root;
        }
        TreeNode nodeLeft = null;
        TreeNode nodeRight = null;
        if (root.left != null){
            nodeLeft = digui(root.left);
        }
        if (root.right != null){
            nodeRight = digui(root.right);
        }

        if (nodeLeft != null){
            nodeLeft.right = root.right;
            root.right = root.left;
        }

        root.left = null;
        if (nodeRight != null){
            return  nodeRight;
        }
        return nodeLeft;
    }