easy understand java solution without recursive


  • 0
    M
    public class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            TreeNode node = root;
            TreeNode pNode = null; //record the parent of the deletnote
            while(node != null){
                if(node.val == key)break;
                pNode = node;
                if(key < node.val){
                    node = node.left;
                }else{
                   node = node.right; 
                } 
            }
            if(node == null)return root;//the tree doesn't contains key
            if(pNode == null)return removeNode(node);//delete the root
            if(pNode.left == node){
                pNode.left = removeNode(node);
            }else{
                pNode.right = removeNode(node);
            }
            return root;
        }
        public TreeNode removeNode(TreeNode root){
            if(root.left == null)return root.right;
            if(root.right == null)return root.left;
            TreeNode node = root.right;
            if(node.left == null){//when the root.right is the min node
                node.left = root.left;
                return node;
            }
            TreeNode pNode=root;//find the min node in the root.right
            while(node.left != null){
                pNode = node;
                node = node.left;
            }
            root.val = node.val;
            pNode.left = node.right;
            return root;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.